cola de prioridad

En informática , una cola de prioridad es un tipo de datos abstracto similar a una cola normal o una estructura de datos de pila . Cada elemento de una cola de prioridad tiene una prioridad asociada. En una cola de prioridad, los elementos con alta prioridad se sirven antes que los elementos con baja prioridad. En algunas implementaciones, si dos elementos tienen la misma prioridad, se entregan en el mismo orden en que fueron puestos en cola. En otras implementaciones, el orden de los elementos con la misma prioridad no está definido.

Si bien las colas de prioridad a menudo se implementan mediante montones , conceptualmente son distintas de los montones. Una cola de prioridad es una estructura de datos abstracta como una lista o un mapa ; Así como una lista se puede implementar con una lista vinculada o con una matriz , una cola de prioridad se puede implementar con un montón u otro método, como una matriz desordenada.

Operaciones

Una cola prioritaria debe admitir al menos las siguientes operaciones:

is_empty : comprueba si la cola no tiene elementos.
insert_with_priority : agrega un elemento a la cola con una prioridad asociada.
pull_highest_priority_element : elimina el elemento de la cola que tiene la prioridad más alta y lo devuelve.
Esto también se conoce como " pop_element(Off) ", " get_maximum_element " o " get_front(most)_element ".
Algunas convenciones invierten el orden de prioridades, considerando que los valores más bajos tienen mayor prioridad, por lo que esto también puede conocerse como " get_minimum_element " y, a menudo, se lo denomina " get-min " en la literatura.
En cambio, esto se puede especificar como funciones separadas " peek_at_highest_priority_element " y " delete_element ", que se pueden combinar para producir " pull_highest_priority_element ".

Además, peek (en este contexto a menudo llamado find-max o find-min ), que devuelve el elemento de mayor prioridad pero no modifica la cola, se implementa con mucha frecuencia y casi siempre se ejecuta en tiempo O (1) . Esta operación y su rendimiento O (1) es crucial para muchas aplicaciones de colas prioritarias.

Las implementaciones más avanzadas pueden admitir operaciones más complicadas, como pull_lowest_priority_element , inspeccionar los primeros elementos de mayor o menor prioridad, borrar la cola, borrar subconjuntos de la cola, realizar una inserción por lotes, fusionar dos o más colas en una, incrementar la prioridad. de cualquier elemento, etc.

Las pilas y colas se pueden implementar como tipos particulares de colas de prioridad, con la prioridad determinada por el orden en que se insertan los elementos. En una pila, la prioridad de cada elemento insertado aumenta monótonamente; por tanto, el último elemento insertado es siempre el primero que se recupera. En una cola, la prioridad de cada elemento insertado disminuye monótonamente; por tanto, el primer elemento insertado es siempre el primero que se recupera.

Implementación

Implementaciones ingenuas

Hay una variedad de formas simples, generalmente ineficientes, de implementar una cola de prioridad. Proporcionan una analogía para ayudar a comprender qué es una cola de prioridad.

Por ejemplo, se pueden mantener todos los elementos en una lista sin ordenar ( O (1) tiempo de inserción). Siempre que se solicite el elemento de mayor prioridad, busque entre todos los elementos el que tenga mayor prioridad. ( O ( n ) tiempo de extracción),

insertar (nodo){ lista.append(nodo)}

jalar (){ más alto = lista.get_first_element() para cada nodo en la lista { si prioridad.más alta <prioridad.nodo { más alto = nodo } } lista.eliminar(más alto) retorno más alto}

En otro caso, se pueden mantener todos los elementos en una lista ordenada por prioridad ( O (n) tiempo de clasificación por inserción), siempre que se solicite el elemento de mayor prioridad, se puede devolver el primero de la lista. ( O (1) tiempo de extracción)

insertar (nodo){ foreach (índice, elemento) en la lista { si nodo.prioridad <elemento.prioridad { list.insert_at_index(nodo,índice) romper } }}

jalar (){ más alto = list.get_at_index(list.length-1) lista.eliminar(más alto) retorno más alto}

Implementación habitual

Para mejorar el rendimiento, las colas de prioridad generalmente se basan en un montón , lo que proporciona un rendimiento O (log n ) para inserciones y eliminaciones, y O ( n ) para construir el montón inicialmente a partir de un conjunto de n elementos. Las variantes de la estructura básica de datos del montón, como los montones de emparejamiento o los montones de Fibonacci , pueden proporcionar mejores límites para algunas operaciones. ^[1]

Alternativamente, cuando se utiliza un árbol de búsqueda binario autoequilibrado , la inserción y eliminación también toman O (log n ) tiempo, aunque construir árboles a partir de secuencias de elementos existentes toma O ( n log n ) tiempo; Esto es típico cuando uno ya puede tener acceso a estas estructuras de datos, como bibliotecas estándar o de terceros. Desde el punto de vista de la complejidad del espacio, el uso de un árbol de búsqueda binario autoequilibrado con lista vinculada requiere más almacenamiento, ya que requiere almacenar referencias adicionales a otros nodos.

Desde el punto de vista de la complejidad computacional, las colas de prioridad son congruentes con los algoritmos de clasificación. La sección sobre la equivalencia de colas de prioridad y algoritmos de clasificación, a continuación, describe cómo los algoritmos de clasificación eficientes pueden crear colas de prioridad eficientes.

Montones especializados

Existen varias estructuras de datos de montón especializadas que proporcionan operaciones adicionales o superan las implementaciones basadas en montón para tipos específicos de claves, específicamente claves enteras. Supongamos que el conjunto de claves posibles es {1, 2, ..., C}.

Cuando solo se necesitan insert , find-min y extract-min y en el caso de prioridades enteras, se puede construir una cola de depósito como una matriz de listas enlazadas en $C$ más un puntero $top$ , inicialmente $C$ . Al insertar un elemento con la clave $k$ , se agrega el elemento a la $k$ 'ésima lista y se actualiza $top \leftarrow min(top,$ $k$ $)$ , ambos en tiempo constante. Extract-min elimina y devuelve un elemento de la lista con índice $top$ , luego incrementa $top$ si es necesario hasta que nuevamente apunte a una lista no vacía; esto lleva $O$ $($ $C$ $)$ tiempo en el peor de los casos. Estas colas son útiles para ordenar los vértices de un gráfico por su grado. ^[2]^{: 374}
Un árbol de Van Emde Boas admite las operaciones mínimo , máximo , insertar , eliminar , buscar , extraer-min , extraer-max , predecesor y sucesor] en tiempo O (log log C ), pero tiene un costo de espacio para colas pequeñas de aproximadamente O (2 ^{m /2} ), donde m es el número de bits en el valor de prioridad. ^[3] El espacio se puede reducir significativamente con hash.
El árbol Fusion de Fredman y Willard implementa la operación mínima en tiempo O (1) y operaciones de inserción y extracción mínima en tiempo. Sin embargo, el autor afirma que "Nuestros algoritmos sólo tienen interés teórico; los factores constantes involucrados en los tiempos de ejecución impiden la practicidad". ^[4] $O(\log n/\log \log C)$

Para las aplicaciones que realizan muchas operaciones de " peek " para cada operación "extract-min", la complejidad temporal de las acciones de peek se puede reducir a O (1) en todas las implementaciones de árbol y montón almacenando en caché el elemento de mayor prioridad después de cada inserción y eliminación. Para la inserción, esto agrega como máximo un costo constante, ya que el elemento recién insertado se compara solo con el elemento mínimo previamente almacenado en caché. Para la eliminación, esto como máximo agrega un costo de "vistazo" adicional, que normalmente es más barato que el costo de eliminación, por lo que la complejidad del tiempo general no se ve significativamente afectada.

Las colas de prioridad monótonas son colas especializadas que están optimizadas para el caso en el que nunca se inserta ningún elemento que tenga una prioridad más baja (en el caso de un montón mínimo) que cualquier elemento extraído previamente. Esta restricción se cumple mediante varias aplicaciones prácticas de colas de prioridad.

Resumen de tiempos de ejecución

A continuación se presentan las complejidades temporales ^[5] de varias estructuras de datos del montón. Los nombres de las funciones suponen un montón mínimo. Para conocer el significado de " O ( f )" y " Θ ( f )", consulte la notación O grande .

^ abcdefghi Tiempo amortizado.
^ Brodal y Okasaki describen una técnica para reducir la complejidad de fusión en el peor de los casos a Θ (1); esta técnica se aplica a cualquier estructura de datos de montón que tenga inserción en Θ (1) y find-min , delete-min , fusione en O (log n ).
^ Límite inferior de ^[9] límite superior de ^[10] $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$
^ Brodal y Okasaki describen más tarde una variante persistente con los mismos límites excepto la tecla de disminución, que no es compatible. Los montones con n elementos se pueden construir de abajo hacia arriba en O ( n ). ^[15]

Equivalencia de colas de prioridad y algoritmos de clasificación.

Usar una cola de prioridad para ordenar

La semántica de las colas de prioridad sugiere naturalmente un método de clasificación: insertar todos los elementos que se ordenarán en una cola de prioridad y eliminarlos secuencialmente; saldrán en orden ordenado. En realidad, este es el procedimiento utilizado por varios algoritmos de clasificación , una vez que se elimina la capa de abstracción proporcionada por la cola de prioridad. Este método de clasificación es equivalente a los siguientes algoritmos de clasificación:

Usar un algoritmo de clasificación para crear una cola prioritaria

También se puede utilizar un algoritmo de clasificación para implementar una cola de prioridad. Específicamente, Thorup dice: ^[17]

Presentamos una reducción de espacio lineal determinista general desde colas de prioridad hasta clasificación, lo que implica que si podemos ordenar hasta n claves en S ( n ) tiempo por clave, entonces hay una cola de prioridad que admite eliminar e insertar en O ( S ( n )) time y find-min en tiempo constante.

Es decir, si hay un algoritmo de clasificación que puede ordenar en tiempo O ( S ) por clave, donde S es alguna función de n y tamaño de palabra , ^[18] entonces se puede usar el procedimiento dado para crear una cola de prioridad donde extraer las El elemento de mayor prioridad es el tiempo O (1), y la inserción de nuevos elementos (y la eliminación de elementos) es el tiempo O ( S ). Por ejemplo, si uno tiene un algoritmo de clasificación O ( n log n ), puede crear una cola de prioridad con O (1) extracción y O (log n ) inserción.

Bibliotecas

A menudo se considera que una cola de prioridad es una " estructura de datos contenedora ".

La biblioteca de plantillas estándar (STL) y el estándar C++ 1998 especifican std::priority_queue como una de las plantillas de clase de adaptador de contenedor STL . Sin embargo, no especifica cómo se deben servir dos elementos con la misma prioridad y, de hecho, las implementaciones comunes no los devolverán según su orden en la cola. Implementa una cola de prioridad máxima y tiene tres parámetros: un objeto de comparación para ordenar, como un objeto de función (por defecto, less<T> si no se especifica), el contenedor subyacente para almacenar las estructuras de datos (por defecto, std::vector <T>), y dos iteradores al principio y al final de una secuencia. A diferencia de los contenedores STL reales, no permite la iteración de sus elementos (se adhiere estrictamente a su definición de tipo de datos abstracto). STL también tiene funciones de utilidad para manipular otro contenedor de acceso aleatorio como un montón máximo binario. Las bibliotecas Boost también tienen una implementación en el montón de bibliotecas.

El módulo heapq de Python implementa un montón mínimo binario encima de una lista.

La biblioteca de JavaPriorityQueue contiene una clase que implementa una cola de prioridad mínima.

La biblioteca de .NET contiene una clase PriorityQueue, que implementa un montón mínimo cuaternario respaldado por una matriz.

La biblioteca de Scala contiene una clase PriorityQueue, que implementa una cola de prioridad máxima.

La biblioteca de Go contiene un módulo contenedor/montón, que implementa un montón mínimo encima de cualquier estructura de datos compatible.

La extensión de la biblioteca PHP estándar contiene la clase SplPriorityQueue.

El marco Core Foundation de Apple contiene una estructura CFBinaryHeap, que implementa un montón mínimo.

Aplicaciones

Gestión de ancho de banda

Las colas de prioridad se pueden utilizar para administrar recursos limitados, como el ancho de banda en una línea de transmisión desde un enrutador de red . En caso de que el tráfico saliente se ponga en cola debido a un ancho de banda insuficiente, se pueden detener todas las demás colas para enviar el tráfico desde la cola de mayor prioridad a su llegada. Esto garantiza que el tráfico priorizado (como el tráfico en tiempo real, por ejemplo, un flujo RTP de una conexión VoIP ) se reenvíe con el menor retraso y la menor probabilidad de ser rechazado debido a que una cola alcanza su capacidad máxima. El resto del tráfico se puede manejar cuando la cola de mayor prioridad está vacía. Otro enfoque utilizado es enviar desproporcionadamente más tráfico desde colas de mayor prioridad.

Muchos protocolos modernos para redes de área local también incluyen el concepto de colas de prioridad en la subcapa de control de acceso a medios (MAC) para garantizar que las aplicaciones de alta prioridad (como VoIP o IPTV ) experimenten una latencia más baja que otras aplicaciones que pueden funcionar con servicio con el mejor esfuerzo . Los ejemplos incluyen IEEE 802.11e (una enmienda a IEEE 802.11 que proporciona calidad de servicio ) y ITU-T G.hn (un estándar para redes de área local de alta velocidad que utilizan cableado doméstico existente ( líneas eléctricas , líneas telefónicas y cables coaxiales ).

Por lo general, se establece una limitación (policía) para limitar el ancho de banda que puede tomar el tráfico de la cola de mayor prioridad, para evitar que los paquetes de alta prioridad bloqueen el resto del tráfico. Por lo general, este límite nunca se alcanza debido a instancias de control de alto nivel, como Cisco Callmanager, que se puede programar para inhibir las llamadas que excederían el límite de ancho de banda programado.

Simulación de eventos discretos

Otro uso de una cola de prioridad es gestionar los eventos en una simulación de eventos discretos . Los eventos se agregan a la cola con su tiempo de simulación utilizado como prioridad. La ejecución de la simulación procede tirando repetidamente de la parte superior de la cola y ejecutando el evento allí.

Ver también : Programación (informática) , teoría de colas

algoritmo de dijkstra

Cuando el gráfico se almacena en forma de lista o matriz de adyacencia, la cola de prioridad se puede utilizar para extraer el mínimo de manera eficiente al implementar el algoritmo de Dijkstra , aunque también se necesita la capacidad de alterar la prioridad de un vértice particular en la cola de prioridad de manera eficiente.

Si, en cambio, se almacena un gráfico como objetos de nodo y se insertan pares de nodos de prioridad en un montón, no es necesario alterar la prioridad de un vértice en particular si se rastrean los nodos visitados. Una vez que se visita un nodo, si vuelve a aparecer en el montón (habiendo tenido un número de prioridad más bajo asociado anteriormente), se elimina y se ignora.

Codificación Huffman

La codificación de Huffman requiere que se obtengan repetidamente los dos árboles de frecuencia más baja. Una cola de prioridad es un método para hacer esto .

Algoritmos de búsqueda "mejor primero"

Los algoritmos de búsqueda del mejor primero , como el algoritmo de búsqueda A* , encuentran el camino más corto entre dos vértices o nodos de un gráfico ponderado , probando primero las rutas más prometedoras. Se utiliza una cola de prioridad (también conocida como franja ) para realizar un seguimiento de las rutas inexploradas; se le da mayor prioridad a aquel para el cual la estimación (un límite inferior en el caso de A*) de la longitud total del camino es la más pequeña. Si las limitaciones de memoria hacen que la búsqueda "mejor primero" no sea práctica, se pueden usar variantes como el algoritmo SMA* , con una cola de prioridad de doble extremo para permitir la eliminación de elementos de baja prioridad.

Algoritmo de triangulación ROAM

El algoritmo de mallas de adaptación óptima ( ROAM ) en tiempo real calcula una triangulación de un terreno que cambia dinámicamente. Funciona dividiendo triángulos donde se necesitan más detalles y fusionándolos donde se necesitan menos detalles. El algoritmo asigna a cada triángulo en el terreno una prioridad, generalmente relacionada con la disminución del error si ese triángulo se dividiera. El algoritmo utiliza dos colas de prioridad, una para los triángulos que se pueden dividir y otra para los triángulos que se pueden fusionar. En cada paso, se divide el triángulo de la cola dividida con la prioridad más alta, o el triángulo de la cola de fusión con la prioridad más baja se fusiona con sus vecinos.

Algoritmo de Prim para árbol de expansión mínimo

Al utilizar la cola de prioridad de montón mínimo en el algoritmo de Prim para encontrar el árbol de expansión mínimo de un gráfico conectado y no dirigido , se puede lograr un buen tiempo de ejecución. Esta cola de prioridad de montón mínimo utiliza la estructura de datos de montón mínimo que admite operaciones como insertar , mínimo , extraer-min , disminuir-clave . ^[19] En esta implementación, el peso de las aristas se utiliza para decidir la prioridad de los vértices . Menor peso, mayor prioridad y mayor peso, menor prioridad. ^[20]

Cola de prioridad paralela

La paralelización se puede utilizar para acelerar las colas de prioridad, pero requiere algunos cambios en la interfaz de la cola de prioridad. La razón de tales cambios es que una actualización secuencial generalmente solo tiene un costo y no existe ningún beneficio práctico para paralelizar dicha operación. Un posible cambio es permitir el acceso simultáneo de múltiples procesadores a la misma cola de prioridad. El segundo cambio posible es permitir operaciones por lotes que funcionen en elementos, en lugar de solo un elemento. Por ejemplo, extractMin eliminará los primeros elementos con mayor prioridad. ${\estilo de texto O(1)}$ ${\estilo de texto O(\log n)}$ ${\estilo de texto k}$ ${\estilo de texto k}$

Acceso paralelo simultáneo

Si la cola de prioridad permite el acceso simultáneo, varios procesos pueden realizar operaciones simultáneamente en esa cola de prioridad. Sin embargo, esto plantea dos cuestiones. En primer lugar, la definición de la semántica de cada una de las operaciones ya no resulta evidente. Por ejemplo, si dos procesos quieren extraer el elemento con mayor prioridad, ¿deberían obtener el mismo elemento o diferentes? Esto restringe el paralelismo en el nivel del programa que utiliza la cola de prioridad. Además, debido a que varios procesos tienen acceso al mismo elemento, esto genera contención.

El acceso simultáneo a una cola de prioridad se puede implementar en un modelo PRAM de lectura y escritura simultáneas (CRCW). A continuación, la cola de prioridad se implementa como una lista de omisión . ^[21]^[22] Además, se utiliza una primitiva de sincronización atómica, CAS , para liberar la lista de omisión de bloqueos . Los nodos de la lista de omisión constan de una clave única, una prioridad, una serie de punteros , para cada nivel, a los siguientes nodos y una marca de eliminación . La marca de eliminación marca si el nodo está a punto de ser eliminado por un proceso. Esto garantiza que otros procesos puedan reaccionar adecuadamente ante la eliminación.

insert(e) : Primero, se crea un nuevo nodo con una clave y una prioridad. Además, al nodo se le asigna una cantidad de niveles, lo que dicta el tamaño de la matriz de punteros. Luego se realiza una búsqueda para encontrar la posición correcta donde insertar el nuevo nodo. La búsqueda comienza desde el primer nodo y desde el nivel más alto. Luego, la lista de omisión se recorre hasta el nivel más bajo hasta encontrar la posición correcta. Durante la búsqueda, para cada nivel, el último nodo atravesado se guardará como nodo principal para el nuevo nodo en ese nivel. Además, el nodo al que apunta el puntero, en ese nivel, del nodo padre, se guardará como nodo sucesor del nuevo nodo en ese nivel. Posteriormente, para cada nivel del nuevo nodo, los punteros del nodo principal se establecerán en el nuevo nodo. Finalmente, los punteros, para cada nivel, del nuevo nodo se establecerán en los nodos sucesores correspondientes.
extract-min : Primero, se recorre la lista de omisión hasta llegar a un nodo cuya marca de eliminación no está establecida. Esta marca de eliminación se establece en verdadero para ese nodo. Finalmente se actualizan los punteros de los nodos principales del nodo eliminado.

Si se permite el acceso simultáneo a una cola de prioridad, pueden surgir conflictos entre dos procesos. Por ejemplo, surge un conflicto si un proceso intenta insertar un nuevo nodo, pero al mismo tiempo otro proceso está a punto de eliminar el predecesor de ese nodo. ^[21] Existe el riesgo de que el nuevo nodo se agregue a la lista de omisión, pero ya no sea accesible. ( Ver imagen )

Operaciones del elemento K

En esta configuración, las operaciones en una cola de prioridad se generalizan a un lote de elementos. Por ejemplo, k_extract-min elimina los elementos más pequeños de la cola de prioridad y los devuelve. ${\estilo de texto k}$ ${\estilo de texto k}$

En una configuración de memoria compartida , la cola de prioridad paralela se puede implementar fácilmente utilizando árboles de búsqueda binarios paralelos y algoritmos de árbol basados en uniones . En particular, k_extract-min corresponde a una división en el árbol de búsqueda binaria que tiene un costo y produce un árbol que contiene los elementos más pequeños. k_insert se puede aplicar mediante una unión de la cola de prioridad original y el lote de inserciones. Si el lote ya está ordenado por clave, k_insert tiene costo. De lo contrario, primero debemos clasificar el lote, por lo que el costo será . Se pueden aplicar de manera similar otras operaciones para la cola prioritaria. Por ejemplo, k_decrease-key se puede hacer aplicando primero diferencia y luego unión , que primero elimina los elementos y luego los inserta nuevamente con las claves actualizadas. Todas estas operaciones son muy paralelas y la eficiencia teórica y práctica se puede encontrar en artículos de investigación relacionados. ^[23]^[24] ${\estilo de texto O(\log n)}$ ${\estilo de texto k}$ ${\textstyle O(k\log(1+{\frac {n}{k}}))}$ ${\textstyle O(k\log(1+{\frac {n}{k}})+k\log k)=O(k\log n)}$

El resto de esta sección analiza un algoritmo basado en colas en memoria distribuida. Suponemos que cada procesador tiene su propia memoria local y una cola de prioridad local (secuencial). Los elementos de la cola de prioridad global (paralela) se distribuyen entre todos los procesadores.

*k_extract-min* se ejecuta en una cola de prioridad con tres procesadores. Los elementos verdes se devuelven y se eliminan de la cola de prioridad.

Una operación k_insert asigna los elementos uniformemente aleatorios a los procesadores que insertan los elementos en sus colas locales. Tenga en cuenta que aún se pueden insertar elementos individuales en la cola. Usando esta estrategia los elementos más pequeños globales están en la unión de los elementos más pequeños locales de cada procesador con alta probabilidad. Por tanto, cada procesador tiene una parte representativa de la cola de prioridad global.

Esta propiedad se utiliza cuando se ejecuta k_extract-min , ya que los elementos más pequeños de cada cola local se eliminan y recopilan en un conjunto de resultados. Los elementos del conjunto de resultados todavía están asociados con su procesador original. El número de elementos que se eliminan de cada cola local depende del número de procesadores . ^[25] Mediante selección paralela se determinan los elementos más pequeños del conjunto de resultados. Con una alta probabilidad, estos son los elementos más pequeños del mundo. De lo contrario, los elementos se eliminan nuevamente de cada cola local y se colocan en el conjunto de resultados. Esto se hace hasta que los elementos globales más pequeños estén en el conjunto de resultados. Ahora estos elementos se pueden devolver. Todos los demás elementos del conjunto de resultados se vuelven a insertar en sus colas locales. Se espera el tiempo de ejecución de k_extract-min , donde y es el tamaño de la cola de prioridad. ^[25] ${\estilo de texto m}$ ${\estilo de texto m}$ ${\estilo de texto k}$ ${\estilo de texto p}$ ${\estilo de texto k}$ ${\estilo de texto k}$ ${\estilo de texto m}$ ${\estilo de texto k}$ ${\estilo de texto k}$ ${\textstyle O({\frac {k}{p}}\log(n))}$ ${\textstyle k=\Omega (p\cdot \log(p))}$ ${\estilo de texto n}$

La cola de prioridad se puede mejorar aún más al no mover los elementos restantes del conjunto de resultados directamente a las colas locales después de una operación k_extract-min . Esto ahorra mover elementos de un lado a otro todo el tiempo entre el conjunto de resultados y las colas locales.

Eliminando varios elementos a la vez se puede conseguir una aceleración considerable. Pero no todos los algoritmos pueden utilizar este tipo de cola de prioridad. El algoritmo de Dijkstra, por ejemplo, no puede funcionar en varios nodos a la vez. El algoritmo toma el nodo con la distancia más pequeña de la cola de prioridad y calcula nuevas distancias para todos sus nodos vecinos. Si eliminara nodos, trabajar en un nodo podría cambiar la distancia de otro de los nodos. Entonces, el uso de operaciones con elementos k destruye la propiedad de configuración de etiquetas del algoritmo de Dijkstra. ${\estilo de texto k}$ ${\estilo de texto k}$

Ver también

Referencias

^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "Capítulo 20: Montones de Fibonacci". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 476–497. ISBN 0-262-03293-7.Tercera edición, pág. 518.
^ Skiena, Steven (2010). El manual de diseño de algoritmos (2ª ed.). Springer Ciencia + Medios comerciales . ISBN 978-1-849-96720-4.
^ P. van Emde Boas. Preservar el orden en un bosque en un tiempo inferior al logarítmico. En Actas del 16º Simposio Anual sobre Fundamentos de la Informática , páginas 75-84. Sociedad de Computación IEEE, 1975.
^ Michael L. Fredman y Dan E. Willard. Superando la teoría de la información ligada a los árboles de fusión. Revista de Ciencias de la Computación y Sistemas , 48(3):533-551, 1994
^ abcd Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. (1990). Introducción a los algoritmos (1ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03141-8.
^ "Montón binomial | Wiki brillante de matemáticas y ciencias". brillante.org . Consultado el 30 de septiembre de 2019 .
^ Brodal, Gerth Stølting; Okasaki, Chris (noviembre de 1996), "Colas de prioridad puramente funcionales óptimas", Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
^ Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. Séptimo taller escandinavo sobre teoría de algoritmos (PDF) , Apuntes de conferencias sobre informática, vol. 1851, Springer-Verlag, págs. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
^ Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia del emparejamiento de montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria de Computación . 46 (4): 473–501. doi :10.1145/320211.320214.
^ Pettie, Seth (2005). Hacia un análisis final de los montones de emparejamiento (PDF) . FOCS '05 Actas del 46º Simposio anual del IEEE sobre fundamentos de la informática. págs. 174-183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (noviembre de 2011). "Montones de emparejamiento de rangos" (PDF) . SIAM J. Informática . 40 (6): 1463–1485. doi :10.1137/100785351.
^ Fredman, Michael Lawrence ; Tarjan, Robert E. (julio de 1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes" (PDF) . Revista de la Asociación de Maquinaria de Computación . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874.
^ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones estrictos de Fibonacci (PDF) . Actas del 44º simposio sobre Teoría de la Computación - STOC '12. págs. 1177-1184. CiteSeerX 10.1.1.233.1740 . doi :10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
^ Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Proc. Séptimo Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 52–58
^ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montón ascendente". Estructuras de datos y algoritmos en Java (3ª ed.). págs. 338–341. ISBN 0-471-46983-1.
^ Takaoka, Tadao (1999), Teoría de 2 a 3 montones (PDF) , p. 12
^ Thorup, Mikkel (2007). "Equivalencia entre colas de prioridad y clasificación". Revista de la ACM . 54 (6): 28. doi :10.1145/1314690.1314692. S2CID 11494634.
^ "Copia archivada" (PDF) . Archivado (PDF) desde el original el 20 de julio de 2011 . Consultado el 10 de febrero de 2011 .{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )
^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. pag. 634.ISBN _ 0-262-03384-4."Para implementar el algoritmo de Prim de manera eficiente, necesitamos una forma rápida de seleccionar una nueva arista para agregarla al árbol formado por las aristas en A".
^ "Algoritmo de Prim". Friki para frikis. 18 de noviembre de 2012. Archivado desde el original el 9 de septiembre de 2014 . Consultado el 12 de septiembre de 2014 .
^ ab Sundell, Håkan; Tsigas, Philippas (2005). "Colas de prioridad simultáneas, rápidas y sin bloqueos para sistemas multiproceso". Revista de Computación Paralela y Distribuida . 65 (5): 609–627. CiteSeerX 10.1.1.67.1310 . doi :10.1109/IPDPS.2003.1213189. S2CID 20995116.
^ Lindén, Jonsson (2013), "Una cola de prioridad simultánea basada en listas de omisión con contención de memoria mínima", Informe técnico 2018-003 (en alemán)
^ Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Simposio sobre arquitecturas y algoritmos paralelos, Proc. del 28º Simposio ACM. Algoritmos y arquitecturas paralelos (SPAA 2016) , ACM, págs. 253–264, arXiv : 1602.02120 , doi : 10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793
^ Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2018), "PAM: mapas aumentados paralelos", Actas del 23º Simposio ACM SIGPLAN sobre principios y práctica de la programación paralela , ACM, págs.
^ ab Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martín; Dementiev, romano (2019). Algoritmos y estructuras de datos secuenciales y paralelos: la caja de herramientas básica . Publicaciones internacionales Springer. págs. 226-229. doi :10.1007/978-3-030-25209-0. ISBN 978-3-030-25208-3. S2CID 201692657.

Otras lecturas

Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "Sección 6.5: Colas prioritarias". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 138-142. ISBN 0-262-03293-7.

enlaces externos

Referencia de C++ para std::priority_queue
Descripciones de Lee Killough
libpqueue es una implementación genérica de cola de prioridad (montón) (en C) utilizada por el proyecto del servidor Apache HTTP.
Estudio de estructuras de colas de prioridad conocidas por Stefan Xenos
UC Berkeley - Ciencias de la Computación 61B - Conferencia 24: Colas de prioridad (vídeo): introducción a las colas de prioridad utilizando el montón binario