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.
Una cola de prioridad ha de soportar al menos las siguientes dos operaciones:
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.
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:
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.
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.
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 en inserción, y de para el desencolado, ya que es la complejidad mínima para buscar en una lista no ordenada).
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 para inserciones y borrados, y de 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 , mientras que la construcción de árboles a partir de secuencias de elementos ya existentes pasaría a tener un coste de .
Desde el punto de vista de la complejidad computacional, las colas de prioridades son congruentes con los algoritmos de búsqueda.
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.
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.
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:
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 claves en tiempo por clave, entonces existe una cola de prioridades que soporta extraer-mínimo e insertar en tiempo , y encontrar-mínimo en tiempo constante.
Esto es, si hay un algoritmo que permita ordenar con coste por cada clave, donde es una función de , existe un procedimiento para crear una cola de prioridad en la que se obtenga el elemento de mayor prioridad en , y se inserten nuevos elementos (y se retiren elementos en el orden de su prioridad) en tiempo . Por ejemplo, si para un cierto conjunto de claves tuviésemos un algoritmo de ordenación con coste para la ordenación de una estructura, podría crearse una cola de prioridades con coste para obtener el elemento de mayor prioridad y con coste para la inserción y borrado en orden.
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:
Partimos a partir de la implementación en Java utilizando clases.