Colas de prioridad

Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.

Este tipo especial de colas tienen las mismas operaciones que las colas FIFO, pero con la condición de que los elementos se atienden en orden de prioridad.

Ejemplos de la vida diaria serían la sala de urgencias de un hospital, ya que los enfermos se van atendiendo en función de la gravedad de su enfermedad.

Entendiendo la prioridad como un valor numérico y asignando a altas prioridades valores pequeños, las colas de prioridad nos permiten añadir elementos en cualquier orden y recuperarlos de menor a mayor.

Hay 2 formas de implementación:

1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

Existe 2 tipos de colas de prioridad:

Colas de prioridades con ordenamiento ascendente: en ellas los elementos se insertan de forma arbitraria, pero a la hora de extraerlos, se extrae el elemento de menor prioridad.

Colas de prioridades con ordenamiento descendente: son iguales que la colas de prioridad con ordenamiento ascendente, pero al extraer el elemento se extrae el de mayor prioridad.

package colaPrioridadSimpleEnlazada;
import colaException.*;

public class ColaPrioridad implements colaPrioridadInterface.ColaPrioridad {
class Celda {
Object elemento;
int prioridad;
Celda sig;
}
private Celda cola;
public ColaPrioridad() {
cola = new Celda();
cola.sig = null;
}
public boolean vacia() {
return (cola.sig==null);
}
public Object primero() throws ColaVaciaException {
if (vacia()) throw new ColaVaciaException();
return cola.sig.elemento;
}
public int primero_prioridad() throws ColaVaciaException {
if (vacia()) throw new ColaVaciaException();
return cola.sig.prioridad;
}
public int primero_prioridad() throws ColaVaciaException {
if (vacia()) throw new ColaVaciaException();
return cola.sig.prioridad;
}
public void inserta(Object elemento, int prioridad) {
Celda p,q;
boolean encontrado = false;
p = cola;
while((p.sig!=null)&&(!encontrado)) {
if (p.sig.prioridad:prioridad)
encontrado = true;
else p = p.sig;
}
q = p.sig;
p.sig = new Celda();
p = p.sig;
p.elemento = elemento;
p.prioridad = prioridad;
p.sig = q;
}
public void suprime() throws ColaVaciaException {
if (vacia()) throw new ColaVaciaException();
cola = cola.sig;
}
} // fin clase ColaPrioridad
[+/-] Ejemplo en Java...