Cola de prioridades
# 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. 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 O(log⁡n){\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 O(log⁡n){\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 O(nlog⁡n){\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.

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:

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

## Implementación en Java

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

