|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectuoc.ei.tads.ColaConPrioridad<E>
public class ColaConPrioridad<E>
Clase que implementa las operaciones de las colas prioritarias (priority queue) y se distingue porque los elementos no se insertan por el final, sino que se ordenan según una prioridad que tienen asociada. Las operaciones de supresión y consulta afectan siempre al elemento que tiene una prioridad más pequeña. En consecuencia, los elementos deberán permitir una operación de comparación de donde se pueda deducir la prioridad. En la representación secuencial del arbol mediante un montículo se organizan los nodos del arbol dentro de de un vector de manera que los hijos y el padre son accesibles aplicando solo una formula. La primera posición del vector contendrá siempre la raíz del arbol que es, precisamente, el elemento más pequeño; si un nodo está en la posición [k], su izquierdo estará a [2*k] y su hijo derecho a [2*k+1].
Nested Class Summary | |
---|---|
protected static class |
ColaConPrioridad.ArbolBinarioQuasicompletoVectorImpl<E>
Clase que extiende el comportamiento de un arbol binario con dos métodos que nos proporcionan la funcionalidad de un arbol cuasicompleto. |
Field Summary | |
---|---|
protected java.util.Comparator<E> |
comparador
Comparador concreto que permite deducir la prioridad entre los elementos. |
protected ColaConPrioridad.ArbolBinarioQuasicompletoVectorImpl<E> |
heap
Arbol binario vector que sirve de apoyo a la cola prioritaria. |
Constructor Summary | |
---|---|
ColaConPrioridad()
Constructor sin parámetros (capacidad máxima, por defecto) y elementos de una clase que implementa java.lang.Comparable. |
|
ColaConPrioridad(java.util.Comparator<E> comparador)
Constructor con un parámetro (capacidad máxima, por defecto) y elementos de una clase comparable con el comparador dado. |
|
ColaConPrioridad(int max)
Constructor con un parámetro (capacidad dada) y elementos de una clase que implementa java.lang.Comparable. |
|
ColaConPrioridad(int max,
java.util.Comparator<E> comparador)
Constructor con dos parámetros (capacidad dada) y elementos de una clase comparable con el comparador dado. |
Method Summary | |
---|---|
protected Posicion<E> |
borrarUltimaPosicion()
|
protected int |
comparar(Posicion<E> pos1,
Posicion<E> pos2)
Método protegido que compara los elementos contenidos en las posiciones recibidas. |
E |
desencolar()
Borra el elemento de menor prioridad, si hay alguno. |
Iterador<E> |
elementos()
Accesor de lectura de los elementos que hay en el contenedor. |
void |
encolar(E elem)
Añade un elemento a la posición que le corresponde, si cabe. |
boolean |
estaLleno()
Método para comprobar si el contenedor está lleno. |
boolean |
estaVacio()
Método para comprobar si el contenedor está vacío. |
protected void |
hundirElemento(Posicion<E> posicioAOrdenar)
|
protected Posicion<E> |
nuevaUltimaPosicion(E elem)
|
int |
numElems()
Accesor de lectura del número de elementos que hay en el contenedor. |
Recorrido |
posiciones()
Método que soporta múltiples recorridos, de las posiciones del contenedor, simultáneos e independientes entre ellos. |
E |
primero()
Accesor de lectura del elemento de menor prioridad, si hay. |
protected void |
subirElemento(Posicion<E> nuevaPosicion)
|
java.lang.String |
toString()
Método que sobrescribe Object.toString(). |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
---|
protected ColaConPrioridad.ArbolBinarioQuasicompletoVectorImpl<E> heap
protected java.util.Comparator<E> comparador
Constructor Detail |
---|
public ColaConPrioridad()
public ColaConPrioridad(int max)
max
- número máximo de elementos que puede contener la colapublic ColaConPrioridad(java.util.Comparator<E> comparador)
comparador
- comparador que permite deducir la prioridadpublic ColaConPrioridad(int max, java.util.Comparator<E> comparador)
max
- número máximo de elementos que puede contener la colacomparador
- comparador que permite deducir la prioridadMethod Detail |
---|
public int numElems()
numElems
in interface Contenedor<E>
public boolean estaVacio()
estaVacio
in interface Contenedor<E>
public boolean estaLleno()
public void encolar(E elem)
encolar
in interface Cola<E>
elem
- elemento comparable que se quiere añadir a la colaprotected Posicion<E> nuevaUltimaPosicion(E elem)
protected void subirElemento(Posicion<E> nuevaPosicion)
public E desencolar()
desencolar
in interface Cola<E>
escogeHijoAIntercambiar(Posicion)
protected Posicion<E> borrarUltimaPosicion()
protected void hundirElemento(Posicion<E> posicioAOrdenar)
public E primero()
primero
in interface Cola<E>
ExcepcionContenedorVacio
- si la cola está vacíapublic Iterador<E> elementos()
elementos
in interface Contenedor<E>
ExcepcionPosicionInvalida
- si se quiere obtener el siguiente
elemento de la enumeración y no hay ningún o no hay ningún
másIterador.haySiguiente()
,
Iterador.siguiente()
public Recorrido posiciones()
public java.lang.String toString()
toString
in class java.lang.Object
protected int comparar(Posicion<E> pos1, Posicion<E> pos2)
pos1
- primera de las dos posiciones de referenciapos2
- segunda de las dos posiciones de referencia
ExcepcionPosicionInvalida
- si alguna posición es null o no
válida
ExcepcioElementsNoComparables
- si alguno de los elementos
contenidos en las posiciones es no comparable
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |