1. No category

ESTRUCTURAS DE DATOS Y ALGORITMOS
Escuela Técnica Superior de Informática Aplicada
Curso 2004-2005
Práctica 7. Implementación de Cola de Prioridad con un
Montı́culo Binario
Duración: 1 sesión
1.
Objetivo de la práctica
El objetivo de esta práctica es que el alumno desarrolle la Implementación de la interfaz Java ColaPrioridad
propuesta en el Tema 4 utilizando la Representación Jerárquica Montı́culo Binario o Heap. Dicha Implementación, además de complementar el estudio teórico del Montı́culo realizado en el Tema 7, se utilizará para
definir el tipo dinámico de la Cola de Prioridad de Eventos que tiene el Simulador del Banco de Modems
desarrollado en la Práctica 5.
2.
Descripción del problema a resolver
Cara a su posterior utilización en la clase Simulador del proyecto bancoDeModems, se desea diseñar la
clase Java MonticuloBinario como Implementación de la interfaz ColaPrioridad que figura a continuación:
package modelos;
public interface ColaPrioridad {
void insertar (Object x);
/* sii !esVacia() */
Object buscarMin ();
/* sii !esVacia() */
Object eliminarMin ();
boolean esVacia ();
}
Se recuerda al alumno que esta interfaz figura ya en el paquete modelosdel proyecto estructurasDeDatosde
libJava.
3.
Actividades en el laboratorio
Los pasos que se recomienda seguir para realizar esta práctica son:
1.
ubicar en el paquete jerarquicos del proyecto estructurasDeDatos de libJava el fichero MonticuloBinario.java
que figura en el directorio /labos/asignaturas/EI/eda/practica7;
2.
completar el código de la clase que contiene MonticuloBinario.java, y que se muestra a continuación,
para que ésta implemente efectivamente ColaPrioridad;
1
package jerarquicos;
/*# completar import*/
public class MonticuloBinario /*# completar aquı́*/ {
protected Object elArray[];
protected int tallaActual ;
protected static final int CAPACIDAD_POR_DEFECTO = 11 ;
public MonticuloBinario(Object infNeg) {
elArray = new Object[CAPACIDAD_POR_DEFECTO + 1];
tallaActual = 0; elArray[0] = infNeg;
}
public void insertar(Object x) {
if ( tallaActual == elArray.length-1 ) duplicarMonticulo();
int hueco = ++tallaActual;
while ( ((Comparable)x).compareTo(elArray[hueco/2]) < 0 ){
elArray[hueco] = elArray[hueco/2]; hueco = hueco/2;
}
elArray[hueco] = x;
}
private void duplicarMonticulo() {
Object [] elArrayAnt = elArray; elArray = new Object[tallaActual*2 + 1];
for ( int i = 0; i < elArrayAnt.length; i++ ) elArray[i] = elArrayAnt[i];
}
private void hundir(int hueco) {
Object aux = elArray[hueco]; int hijo = hueco*2; boolean esHeap = false;
while ( hijo <= tallaActual && !esHeap){
if ( hijo != tallaActual &&
((Comparable)elArray[hijo+1]).compareTo(elArray[hijo]) < 0 )
hijo++;
if ( ((Comparable)elArray[hijo]).compareTo(aux) < 0 ){
elArray[hueco] = elArray[hijo]; hueco = hijo; hijo = hueco*2;
} else esHeap = true;
}
elArray[hueco] = aux;
}
public String toString(){
String res = "*"; for ( int i = 1; i <= tallaActual; i++ ) res += elArray[i] + "*";
return res;
}
/*# completar a partir de aquı́ */
}
3.
tras compilar la clase, se deberá de comprobar su funcionamiento en algún caso sencillo: por ejemplo,
trabajar con un Montı́culo de objetos de la clase Double; para ello, se creará desde el entorno BleuJ
un objeto MonticuloBinario especificando como argumento del constructor, new Double(-500), es
decir, se trabajará con enteros mayores que -500; seguidamente se invocará el método insertar para
introducir el dato 5 en este Montı́culo (new Double(5) como argumento); una llamada al método
buscarMin permitirá comprobar que nos devuelve Double de valor 5.
4.
finalmente se utilizará la clase MonticuloBinario como Implementación de la Cola de Prioridad de
la clase Simulador del proyecto bancoDeModems, realizando las oportunas modificaciones que ello
conlleve.
4.
Ampliación
Diseñese un experimento para comprobar experimentalmente que el coste de las operaciones de una
Cola de Prioridad representada como un Montı́culo se ajusta a los estudiados en el Tema 7. Para ello se
propone contar los compareTo que se realizan en promedio al insertar y borrar (eliminarMin) los Datos de
Colecciones de diferentes tallas y caracterı́sticas.
2