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.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).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).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.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 depara el desencolado, ya que es la complejidad mínima para buscar en una lista no ordenada).Existen ciertos tipos especializados de montículos, como los montículos de Fibonacci, que pueden ofrecer mejores cotas asintóticas para algunas operaciones.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 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.por clave, entonces existe una cola de prioridades que soporta extraer-mínimo e insertar en tiempo[3]​ Esto es, si hay un algoritmo que permita ordenar con costepara obtener el elemento de mayor prioridad y con coste