Cola de prioridades

Una cola de prioridades es un tipo de dato abstracto similar a una cola en la que los elementos tienen adicionalmente, una prioridad asignada.^[1]^[2] En una cola de prioridades un elemento con mayor prioridad será desencolado antes que un elemento de menor prioridad. Si dos elementos tienen la misma prioridad, se desencolarán siguiendo el orden de cola.

Operaciones

Una cola de prioridad ha de soportar al menos las siguientes dos operaciones:

Añadir con prioridad: se añade un elemento a la cola, con su correspondiente prioridad.
Eliminar elemento de mayor prioridad: se devuelve y elimina el elemento con mayor prioridad más antiguo que no haya sido desencolado de la cola.

Además suele implementarse una función frente (que habitualmente aquí se denomina encontrar-máximo o encontrar-mínimo), y que habitualmente se ejecuta en tiempo O(1). Esta operación y su rendimiento en tiempo es crucial en ciertas aplicaciones de las colas de prioridades.

Ciertas implementaciones avanzadas pueden incluir operaciones más complejas para la inspección de los elementos de mayor o menor prioridad, borrar la cola o ciertos subconjuntos de la cola, realizar inserciones en masa, la fusión de dos colas en una, aumentar la prioridad de los elementos, etc.

Características generales

Podrían verse a las colas de prioridades como colas modificadas, en las que en lugar de obtener el siguiente elemento de la cola, se obtiene elemento de mayor prioridad en la cola. De hecho, pilas y colas pueden ser vistas como tipos particulares de colas de prioridad. Para facilitar la lectura, se resume aquí el comportamiento de pilas y colas:

en una pila los elementos son recuperados en orden LIFO (lo último en entrar es lo primero en salir)
en una cola los elementos son recuperados en orden FIFO (lo primero en entrar es lo primero en salir)

Una pila podría verse como una cola de prioridades en la que los elementos son insertados en orden monótono creciente; y por tanto el último elemento insertado es siempre el primero en ser recuperado (ya que tendrá la máxima prioridad hasta el momento). En una cola, la prioridad de cada elemento insertado es monótona decreciente; y por tanto el primer elemento insertado es siempre el primero en ser recuperado (pues todos los elementos subsiguientes tendrán prioridades inferiores).

Un símil con la vida real podría ser la atención de enfermos en la sala de urgencias de un hospital. Podría verse la asignación de enfermos a la cola de enfermos por atender como una cola de prioridades, en las que son atendidos por orden de llegada y a la vez en función de la gravedad de su enfermedad. Aquí, el triaje sería la operación que permitiría conocer la prioridad con la que introducir al enfermo en la cola.

Implementación

Como con cualquier tipo de dato abstracto, una cola de prioridades puede tener múltiples implementaciones, siempre que cumplan las restricciones y el modelo formalizado. A continuación se distinguen implementaciones sencillas frente a otras más especializadas y, también, más habituales para las estructuras de datos que modelen colas de prioridad.

Implementaciones ingenuas

Hay muchas formas de implementar de forma sencilla, aunque a menudo ineficientemente, una cola de prioridades. A pesar de su ineficiencia, pueden ser muy útiles para observar la analogía con la realidad y comprender el funcionamiento abstracto de una cola de prioridades. Por ejemplo, una implementación posible sería mantener todos los elementos en una lista no ordenada. Cuando se pida el elemento con mayor prioridad, se buscan todos los elementos hasta encontrar el de mayor prioridad (la complejidad de esta estructura tendría, según la notación O grande complejidad computacional de $O(1)$ en inserción, y de $O(n)$ para el desencolado, ya que es la complejidad mínima para buscar en una lista no ordenada).

Implementación con montículos

Para mejorar el rendimiento, las colas de prioridades suelen implementarse utilizando un montículo como estructura de datos subyacente, y obteniendo así un rendimiento de ${\textstyle O(\log {n})}$ para inserciones y borrados, y de $O(n)$ para la construcción inicial. Existen ciertos tipos especializados de montículos, como los montículos de Fibonacci, que pueden ofrecer mejores cotas asintóticas para algunas operaciones.

En lugar de un montículo, puede utilizarse un árbol binario de búsqueda auto-balanceable, en cuyo caso la inserción y borrado siguen teniendo un coste de ${\textstyle O(\log {n})}$ , mientras que la construcción de árboles a partir de secuencias de elementos ya existentes pasaría a tener un coste de ${\textstyle O(n\log {n})}$ .

Desde el punto de vista de la complejidad computacional, las colas de prioridades son congruentes con los algoritmos de búsqueda.

Montículos especializados

Existen diversos tipos de montículos especializados que, o bien permiten operaciones adicionales, o bien tienen un rendimiento mejor que otros montículos para ciertos tipos de claves (representando la prioridad), y específicamente cuando las prioridades son números enteros.

Cuando el conjunto de claves es el conjunto conocido y finito $\{1,2,\ldots ,C\}$ , y solo se necesitan las funciones de insertar, encontrar-mínimo, y extraer-mínimo, puede construirse una cola de prioridades de altura limitada implementada como un vector de $C$ listas enlazadas junto con un entero apuntando a la lista superior, inicialmente $C$ . La inserción de un elemento de clave $k$ introduce el elemento en la $k$ -ésima lista, y establece $\mathrm {superior} \leftarrow \min(\mathrm {superior} ,k)$ , ambos en tiempo constante. Extraer-mínimo borra y devuelve el primer elemento de la lista de la prioridad establecida por el índice superior, que es incrementado hasta que apunte a una lista no vacía de nuevo, lo que lleva $O(C)$ tiempo en el peor caso. Puede verse un caso útil de este tipo de colas para la ordenación de vértices de un grafo en función de su grado.
Para el mismo conjunto $\{1,2,\ldots ,C\}$ , un árbol de van Emde Boas podría admitir las operaciones de mínimo, máximo, insertar, eliminar, buscar, extraer-mínimo, extraer-máximo, predecesor y sucesor con un coste de $O(\log \log C)$ , aunque tiene un coste espacial para colas pequeñas de un $O(2^{m/2})$ , para m número de bits de prioridad posibles.

Para aplicaciones que realicen una gran cantidad de operaciones de encontrar-mínimo por cada operación de extraer-mínimo, la complejidad temporal de las acciones de encontrar-mínimo puede reducirse a O(1) en todas las implementaciones de árboles y montículos, almacenando en la estructura el elemento con mayor prioridad después de cada inserción y borrado (a modo de caché). Para la inserción, esto tendrá un coste a lo sumo constante, ya que cada elemento nuevo insertado solo ha de compararse con el actual mínimo (ya cacheado). Para el borrado, esto añade como máximo el coste de encontrar-mínimo que, en general, es menos costoso que el propio borrado, por lo que el comportamiento temporal asintótico no se ve afectado, y el rendimiento práctico tampoco lo hará en general.

Equivalencia entre colas de prioridad y algoritmos de ordenación

Una cola de prioridad como sistema de ordenación

La semántica operacional de las colas de prioridades sugieren un mecanismo natural de ordenación: insertar todos los elementos en la cola de prioridad, y eliminarlos uno a uno: serán devueltos en orden. En realidad, este procedimiento es utilizado por diversos algoritmos de ordenamiento, una vez se elimina la abstracción de la cola de prioridades. Este método de ordenación es equivalente a los siguientes algoritmos de ordenación:

Algoritmo de ordenamiento	Implementación cola de prioridades	Mejor	Media	Peor
Heapsort	Montículo	$n\log(n)$	$n\log(n)$	$n\log(n)$
Smoothsort	Montículo de Leonardo	$n$	$n\log(n)$	$n\log(n)$
Ordenamiento por selección	Array sin ordenar	$n^{2}$	$n^{2}$	$n^{2}$
Ordenamiento por inserción	Array ordenado	$n$	$n^{2}$	$n^{2}$
Ordenamiento con árbol binario	Árbol binario de búsqueda auto-balanceable	$n\log(n)$	$n\log(n)$	$n\log(n)$

Un algoritmo de ordenación como cola de prioridades

Un algoritmo de ordenamiento también puede ser utilizado para implementar una cola de prioridades. Respecto a esto Throup publicó un artículo en 2007 en el que presentó una reducción de la representación de las colas de prioridades a la ordenación mediante una implicación por la cual si pueden ordenarse $n$ claves en tiempo $S(n)$ por clave, entonces existe una cola de prioridades que soporta extraer-mínimo e insertar en tiempo $O(S(n))$ , y encontrar-mínimo en tiempo constante.^[3]

Esto es, si hay un algoritmo que permita ordenar con coste $O(S)$ por cada clave, donde $S$ es una función de $n$ , existe un procedimiento para crear una cola de prioridad en la que se obtenga el elemento de mayor prioridad en $O(1)$ , y se inserten nuevos elementos (y se retiren elementos en el orden de su prioridad) en tiempo $O(S)$ . Por ejemplo, si para un cierto conjunto de claves tuviésemos un algoritmo de ordenación con coste $O(n\log \log n)$ para la ordenación de una estructura, podría crearse una cola de prioridades con coste $O(1)$ para obtener el elemento de mayor prioridad y con coste $O(\log \log n)$ para la inserción y borrado en orden.

Implementación en Maude

Para la implementación de las colas de prioridad el elemento a insertar tiene que ser de un tipo que soporte un orden total y eso lo conseguimos creando una teoría, que será la siguiente:

***( Vamos a manejar explicitamente las prioridades dentro de la cola, por lo que precisamos
que el tipo base proporcione operaciones para acceder a la prioridad, y para compararlas.

Se asume que p1 > p2, donde p1 y p2 son prioridades, significa que p1 es preferente
frente a p2, esto es, un elemento con prioridad p1 es más prioritario que otro con prioridad p2.
)

fth ELEMENTO-PRIORIDAD is
  protecting BOOL .
  sorts Elt Prioridad .  
*** operaciones
 op prioridad : Elt -> Prioridad .
 op _>_ : Prioridad Prioridad -> Bool.
endfth

Una vez que tenemos la teoría procedemos a la implementación de la cola de prioridad:

fmod COLA-PRIORIDAD {X :: ELEMENTO-PRIORIDAD} is
 sorts Cola PrioNV{X} ColaPrio{X} .
 subsort Cola PrioNV{X} < ColaPrio{X} .
*** operaciones
 op crear : -> Cola PrioNV{X} .
 op encolar : X$Elt Cola Prio{X} -> Cola PrioNV{X} [ctor] .
*** constructores
 op desencolar : Cola Prio{X} -> Cola {X} .
*** selectores
 op frente : Cola PrioNV{X} -> X$Elt .
*** variables
 var C : Cola PrioNV{X} .
 var E : X$Elt .
*** ecuaciones
 eq desencolar(crear) = crear .
 eq desencolar(encolar(E,crear)) = crear .
 eq desencolar(encolar(E,C)) = 
       if prioridad(E) > prioridad(frente(C)) then
          C
       else
          encolar(E,desencolar(C))
       fi .
 eq frente(encolar(E,crear)) = E .
 eq frente(encolar(E,C)) =
       if prioridad(E) > prioridad(frente(C)) then
          E
       else
          frente(C)
       fi .
 endfm

Posible instanciación

***( Usamos pares de naturales, en la que el primer valor
es un dato, y el segundo su prioridad. Suponemos que un valor natural más pequeño
indica mayor prioridad.
)

fmod PAR-NAT is
	protecting NAT .
	sort ParNat .
  	
  	op <_:_> : Nat Nat -> ParNat .
  	op info : ParNat -> Nat .
  	op clave : ParNat -> Nat .
  	
  	vars E C : Nat .
  	vars P1 P2 : ParNat .
  	
  	eq info(< E : C >) = E .
	eq clave(< E : C >) = C .
endfm

*** Realizamos la vista correspondiente

view VParNat from ELEMENTO-PRIORIDAD to PAR-NAT is
	sort Elt to ParNat .
	sort Prioridad to Nat .
	op prioridad to clave .
	op _>_ to _<_ .
endv

*** Procedemos a la instanciación

fmod COLA-PAR-NAT is
	protecting COLA-PRIORIDAD{VParNat} .
endfm

Ejemplo Cola Prioridad en Maude

 COLA-MEDIEVAL es un ejemplo de colas de prioridad en la que los elemento de la cola son
plebeyos y nobles, en la cual la prioridad la tienen los nobles.

 fth MEDIEVAL is
	sort Elt .
	op esNoble?: Elt --> Bool .
 endfth

 fmod COLA-MEDIEVAL {x::MEDIEVAL} is
	protecting NAT, BOOL .
	sort colaM{x} .
	subsort colaMNV{x} < colaM{x} .
	
	op crear: --> colaM{x} [ctor] .
	op insertar: x$Elt colaM{x} --> colaMNV{x} [ctor] .

	op extraer: colaM{x} --> colaM{x} .
	op frente: colaMNV{x} --> x$Elt .
	op NNobles: colaM{x} --> Nat .
	op NPlebleyos: colaM{x} --> Nat .

	var C: colaMNV{x} .
	var E: x$Elt .

	eq extraer(crear) = crear .
	eq extraer(insertar(E,crear)) = crear .
	eq extraer(insertar(E,C)) = if NOT(esNoble?(frente(c))) AND esNoble?(E) then
					c
				    else
					insertar(E,extraer(c))
				    fi .
	
	eq frente(insertar(E,crear)) = E .
	eq frente(insertar(E,C)) = if (esNoble?(E)) AND (esNoble?(frente(C))) then
					E
				   else
					frente(C)
				   fi .

	eq NNobles(crear) = 0 .
	eq NNobles(insertar(E,C)) = if esNobles?(E) then
					1 + NNobles(C)
				    else
					NNobles(C)
				    fi .

	
	eq NPlebleyos(crear) = 0 .
	eq NPlebleyos(insertar(E,C)) = if NOT(esNobles?(E)) then
					1 + NPlebeyos(C)
				    else
					NPlebeyos(C)
				    fi .
 endfm

Implementación en Java

Partimos a partir de la implementación en Java utilizando clases.

package colaPrioridadSimpleEnlazada;
import colaException.*;

public class ColaPrioridad<T> implements colaPrioridadInterface.ColaPrioridad {
    class Celda<T> {
        T elemento;
        int prioridad;
        Celda sig;
    }
    private Celda cola;
    public ColaPrioridad() {
        cola = new Celda();
        cola.sig = null;
    }
    public boolean vacia() {
        return (cola.sig==null);
    } 
    public <T> 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 void inserta(T elemento, int prioridad) {
        Celda<T> 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

Referencias

↑ Introduction to Algorithms, 3rd Edition (en inglés) (3rd edition edición). The MIT Press. 31 de julio de 2009. ISBN 9780262033848. Consultado el 9 de enero de 2016.
↑ The Algorithm Design Manual (en inglés) (2nd edition edición). Springer. 26 de julio de 2008. ISBN 9781848000698. Consultado el 9 de enero de 2016.
↑ Thorup, Mikkel (1 de diciembre de 2007). «Equivalence Between Priority Queues and Sorting». J. ACM 54 (6). ISSN 0004-5411. doi:10.1145/1314690.1314692. Consultado el 9 de enero de 2016.

Véase también

Enlaces externos

Descripción de Lee Killough

Datos: Q629283

[1] Introduction to Algorithms, 3rd Edition (en inglés) (3rd edition edición). The MIT Press. 31 de julio de 2009. ISBN 9780262033848. Consultado el 9 de enero de 2016.

[2] The Algorithm Design Manual (en inglés) (2nd edition edición). Springer. 26 de julio de 2008. ISBN 9781848000698. Consultado el 9 de enero de 2016.

[3] Thorup, Mikkel (1 de diciembre de 2007). «Equivalence Between Priority Queues and Sorting». J. ACM 54 (6). ISSN 0004-5411. doi:10.1145/1314690.1314692. Consultado el 9 de enero de 2016.

[1]

[2]

[3]