Cola de prioridad
Tipos de datos abstractos en informática

En informática , una cola de prioridad es un tipo de datos abstracto similar a una cola normal o un tipo de datos abstracto 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 sirven en el mismo orden en el que se pusieron en cola. En otras implementaciones, el orden de los elementos con la misma prioridad no está definido.

Si bien las colas de prioridad suelen implementarse mediante heaps , conceptualmente son distintas de los heaps. Una cola de prioridad es un tipo de datos abstracto como una lista o un mapa ; así como una lista se puede implementar con una lista enlazada o con una matriz , una cola de prioridad se puede implementar con un heap u otro método como una matriz ordenada.

Operaciones

Una cola de prioridad debe admitir al menos las siguientes operaciones:

  • is_empty : verifica 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 puede especificarse como funciones independientes " peek_at_highest_priority_element " y " delete_element ", que pueden combinarse para producir " pull_highest_priority_element ".

Además, la operación peek (en este contexto, a menudo denominada 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) son cruciales para muchas aplicaciones de colas de prioridad.

Las implementaciones más avanzadas pueden soportar operaciones más complicadas, como pull_lowest_priority_element , inspeccionar los primeros elementos de mayor o menor prioridad, limpiar la cola, limpiar 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 las colas se pueden implementar como tipos particulares de colas de prioridad, en las que la prioridad se determina por el orden en el que se insertan los elementos. En una pila, la prioridad de cada elemento insertado aumenta de forma monótona; por lo tanto, el último elemento insertado es siempre el primero en recuperarse. En una cola, la prioridad de cada elemento insertado disminuye de forma monótona; por lo tanto, el primer elemento insertado es siempre el primero en recuperarse.

Implementación

Implementaciones ingenuas

Existen diversas formas sencillas, generalmente ineficientes, de implementar una cola de prioridad. Estas proporcionan una analogía que ayuda a comprender qué es una cola de prioridad.

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

insertar (nodo) { lista.append(nodo)}
jalar () { más alto = lista.obtener_primer_elemento() foreach nodo en lista { si mayor prioridad < nodo.prioridad { más alto = nodo } } lista.eliminar(más alta) volver más alto}

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

insertar (nodo) { foreach (índice, elemento) en lista { si nodo.prioridad < elemento.prioridad { lista.insert_at_index(nodo,índice) romper } }}
jalar () { más alto = lista.obtener_en_índice(lista.longitud-1) lista.eliminar(más alta) volver más alto}

Implementación habitual

Para mejorar el rendimiento, las colas de prioridad se basan normalmente en un montón , lo que proporciona un rendimiento de 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 de datos del montón básico, 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 binario de búsqueda autoequilibrado , la inserción y la eliminación también toman tiempo O (log n ), aunque la construcción de árboles a partir de secuencias existentes de elementos toma tiempo O ( n log n ); esto es típico donde uno ya podría tener acceso a estas estructuras de datos, como con bibliotecas de terceros o estándar. Desde un punto de vista de complejidad espacial, el uso de un árbol binario de búsqueda autoequilibrado con lista enlazada 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 ordenamiento. La sección sobre la equivalencia de las colas de prioridad y los algoritmos de ordenamiento, que aparece a continuación, describe cómo los algoritmos de ordenamiento eficientes pueden crear colas de prioridad eficientes.

Montones especializados

Existen varias estructuras de datos de montón especializadas que proporcionan operaciones adicionales o superan a 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 caso de prioridades enteras, se puede construir una cola de cubos como una matriz de listas enlazadas C más un puntero top , inicialmente C . Insertar un elemento con clave k agrega el elemento a la lista k 'th y actualiza top ← 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 toma 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 , inserción , eliminación , búsqueda , extracción mínima , extracción máxima , 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 la cantidad de bits en el valor de prioridad. [3] El espacio se puede reducir significativamente con hash.
  • El árbol de fusión de Fredman y Willard implementa la operación mínima en tiempo O (1) y las operaciones de inserción y extracción mínimas en tiempo. Sin embargo, el autor afirma que "nuestros algoritmos tienen un interés teórico únicamente; los factores constantes involucrados en los tiempos de ejecución impiden su aplicación práctica". [4] Oh ( registro ⁡ norte / registro ⁡ registro ⁡ do ) {\displaystyle O(\log n/\log \log C)}

Para las aplicaciones que realizan muchas operaciones de " vista previa " por cada operación de "extracción mínima", la complejidad temporal de las acciones de vista previa se puede reducir a O (1) en todas las implementaciones de árboles y montones 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 almacenado previamente en caché. Para la eliminación, esto agrega como máximo un costo de "vista previa" adicional, que generalmente es más económico que el costo de eliminación, por lo que la complejidad temporal general no se ve afectada significativamente.

Las colas de prioridad monótona son colas especializadas que están optimizadas para el caso en el que nunca se inserta ningún elemento que tenga una prioridad menor (en el caso de min-heap) que cualquier elemento extraído previamente. Esta restricción se cumple en varias aplicaciones prácticas de las colas de prioridad.

Resumen de tiempos de ejecución

Aquí se muestran las complejidades temporales [5] de varias estructuras de datos de montón. La abreviatura am. indica que la complejidad dada se amortiza, de lo contrario es una complejidad del peor caso. Para el significado de " O ( f )" y " Θ ( f )", consulte la notación Big O. Los nombres de las operaciones suponen un montón mínimo.

Operaciónencontrar-mineliminar-mintecla de disminucióninsertarfusionarsecrear montón [a]
Binario [5]Θ (1)Θ (log  n )Θ (log  n )Θ (log  n )Θ ( n )Θ ( n )
Inclinación [6]Θ (1)O (log  n ) soy.O (log  n ) soy.O (log  n ) soy.O (log  n ) soy.Θ ( n ) soy.
Izquierdista [7]Θ (1)Θ (log  n )Θ (log  n )Θ (log  n )Θ (log  n )Θ ( n )
Binomio [5] [9]Θ (1)Θ (log  n )Θ (log  n )Yo (1) soy.Θ (log  n ) [b]Θ ( n )
Binomio sesgado [10]Θ (1)Θ (log  n )Θ (log  n )Θ (1)Θ (log  n ) [b]Θ ( n )
Montón de 2 a 3 [12]Θ (1)O (log  n ) soy.Θ (1)Yo (1) soy.O (log  n ) [b]Θ ( n )
Sesgo de abajo hacia arriba [6]Θ (1)O (log  n ) soy.O (log  n ) soy.Yo (1) soy.Yo (1) soy.Θ ( n ) soy.
Emparejamiento [13]Θ (1)O (log  n ) soy.o (log  n ) soy. [c]Θ (1)Θ (1)Θ ( n )
Emparejamiento de rangos [16]Θ (1)O (log  n ) soy.Yo (1) soy.Θ (1)Θ (1)Θ ( n )
Fibonacci [5] [17]Θ (1)O (log  n ) soy.Yo (1) soy.Θ (1)Θ (1)Θ ( n )
Fibonacci estricto [18] [d]Θ (1)Θ (log  n )Θ (1)Θ (1)Θ (1)Θ ( n )
Brodal [19] [d]Θ (1)Θ (log  n )Θ (1)Θ (1)Θ (1)Θ ( n ) [20]
  1. ^ make-heap es la operación de construir un montón a partir de una secuencia de n elementos no ordenados. Se puede realizar en Θ ( n ) tiempo siempre que meld se ejecute en O (log  n ) tiempo (donde ambas complejidades se pueden amortizar). [6] [7] Otro algoritmo logra Θ ( n ) para montones binarios. [8]
  2. ^ abc Para los montículos persistentes (que no admiten decrease-key ), una transformación genérica reduce el costo de meld al de insert , mientras que el nuevo costo de delete-min es la suma de los costos anteriores de delete-min y meld . [11] Aquí, hace que meld se ejecute en Θ (1) tiempo (amortizado, si el costo de insert es) mientras que delete-min todavía se ejecuta en O (log  n ). Aplicado a montículos binomiales sesgados, produce colas Brodal-Okasaki, montículos persistentes con complejidades óptimas en el peor de los casos. [10]
  3. ^ Límite inferior de [14] límite superior de [15] Ohmio ( registro ⁡ registro ⁡ norte ) , {\displaystyle \Omega (\log \log n),} Oh ( 2 2 registro ⁡ registro ⁡ norte ) . {\displaystyle O(2^{2{\sqrt {\log \log n}}}).}
  4. ^ Las colas de Brodal y los montículos de Fibonacci estrictos logran complejidades óptimas en el peor de los casos para los montículos. Primero se describieron como estructuras de datos imperativas. La cola de Brodal-Okasaki es una estructura de datos persistente que logra el mismo óptimo, excepto que no se admite la clave de disminución .

Equivalencia de colas de prioridad y algoritmos de ordenación

Usando una cola de prioridad para ordenar

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

NombreImplementación de cola de prioridadMejorPromedioEl peor
Ordenamiento por montículosMontón norte registro ⁡ ( norte ) {\estilo de visualización n\log(n)} norte registro ⁡ ( norte ) {\estilo de visualización n\log(n)} norte registro ⁡ ( norte ) {\estilo de visualización n\log(n)}
Ordenación suaveMontón de Leonardo norte {\estilo de visualización n} norte registro ⁡ ( norte ) {\estilo de visualización n\log(n)} norte registro ⁡ ( norte ) {\estilo de visualización n\log(n)}
Ordenación por selecciónMatriz desordenada norte 2 {\estilo de visualización n^{2}} norte 2 {\estilo de visualización n^{2}} norte 2 {\estilo de visualización n^{2}}
Ordenación por inserciónMatriz ordenada norte {\estilo de visualización n} norte 2 {\estilo de visualización n^{2}} norte 2 {\estilo de visualización n^{2}}
Ordenación de árbolesÁrbol de búsqueda binario autoequilibrado norte registro ⁡ ( norte ) {\estilo de visualización n\log(n)} norte registro ⁡ ( norte ) {\estilo de visualización n\log(n)} norte registro ⁡ ( norte ) {\estilo de visualización n\log(n)}

Utilizando un algoritmo de ordenación para crear una cola de prioridad

También se puede utilizar un algoritmo de ordenación para implementar una cola de prioridad. En concreto, Thorup afirma: [21]

Presentamos una reducción espacial lineal determinista general desde colas de prioridad hasta ordenación, lo que implica que si podemos ordenar hasta n claves en tiempo S ( n ) por clave, entonces hay una cola de prioridad que admite eliminación e inserción en tiempo O ( S ( n )) y búsqueda mínima en tiempo constante.

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

Bibliotecas

Una cola de prioridad a menudo se considera una " estructura de datos contenedora ".

La biblioteca de plantillas estándar (STL) y el estándar C++ 1998 especifica 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 máxima prioridad y tiene tres parámetros: un objeto de comparación para ordenar, como un objeto de función (el valor predeterminado es less<T> si no se especifica), el contenedor subyacente para almacenar las estructuras de datos (el valor predeterminado es std::vector<T>) y dos iteradores para el comienzo y el 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 abstractos). 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 min-heap binario en la parte superior de una lista.

La biblioteca de JavaPriorityQueue contiene una clase que implementa una cola de prioridad mínima como un montón binario.

La biblioteca de .NET contiene una clase PriorityQueue, que implementa un min-heap cuaternario respaldado por una matriz.

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

La biblioteca de Go contiene un módulo contenedor/montón, que implementa un min-montón sobre 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 min-heap.

Aplicaciones

Gestión del ancho de banda

La cola de prioridad se puede utilizar para gestionar 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, todas las demás colas se pueden detener 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. Todo el resto del tráfico se puede gestionar 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 al medio (MAC) para garantizar que las aplicaciones de alta prioridad (como VoIP o IPTV ) experimenten una latencia menor que otras aplicaciones que pueden recibir un servicio de máximo esfuerzo . Algunos ejemplos incluyen IEEE 802.11e (una modificación de IEEE 802.11 que proporciona calidad de servicio ) e ITU-T G.hn (una norma para redes de área local de alta velocidad que utilizan el cableado doméstico existente ( líneas eléctricas , líneas telefónicas y cables coaxiales ).

Generalmente se establece una limitación (policía) para limitar el ancho de banda que puede utilizar el tráfico de la cola de mayor prioridad, con el fin de evitar que los paquetes de alta prioridad obstruyan el resto del tráfico. Este límite normalmente nunca se alcanza debido a instancias de control de alto nivel como Cisco Callmanager, que se pueden programar para inhibir las llamadas que excedan 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 añaden a la cola y su tiempo de simulación se utiliza como prioridad. La ejecución de la simulación se lleva a cabo extrayendo repetidamente la parte superior de la cola y ejecutando el evento que se encuentra allí.

Véase 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, se puede utilizar una cola de prioridad 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, un gráfico se almacena como objetos de nodo y se insertan pares de nodos prioritarios en un montón, no es necesario modificar la prioridad de un vértice en particular si se hace un seguimiento de 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 con él anteriormente), se lo elimina y se lo ignora.

Codificación de 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 lograrlo .

Algoritmos de búsqueda que priorizan lo mejor

Los algoritmos de búsqueda de mejor primero , como el algoritmo de búsqueda A* , encuentran la ruta más corta 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; aquella para la que la estimación (un límite inferior en el caso de A*) de la longitud total de la ruta es más pequeña recibe la mayor prioridad. Si las limitaciones de memoria hacen que la búsqueda de mejor primero sea poco práctica, se pueden utilizar en su lugar 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 ROAM (Real-time Optimally Adapting Meshes ) calcula una triangulación de un terreno que cambia dinámicamente. Funciona dividiendo los triángulos donde se necesitan más detalles y fusionándolos donde se necesitan menos detalles. El algoritmo asigna a cada triángulo del 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 de división con la prioridad más alta, o se fusiona el triángulo de la cola de fusión con la prioridad más baja con sus vecinos.

Algoritmo de Prim para el árbol de expansión mínima

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-mínimo , disminuir-clave . [23] En esta implementación, el peso de los bordes se utiliza para decidir la prioridad de los vértices . Cuanto menor sea el peso, mayor será la prioridad y cuanto mayor sea el peso, menor será la prioridad. [24]

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 estos cambios es que una actualización secuencial normalmente solo tiene un costo y no hay ninguna ganancia práctica en paralelizar una operación de este tipo. Un cambio posible es permitir el acceso simultáneo de varios procesadores a la misma cola de prioridad. El segundo cambio posible es permitir operaciones por lotes que funcionen sobre elementos, en lugar de solo sobre un elemento. Por ejemplo, extractMin eliminará los primeros elementos con la prioridad más alta. Oh ( 1 ) {\textstyle O(1)} Oh ( registro ⁡ norte ) {\textstyle O(\log n)} a {\textstyle k} a {\textstyle k}

Acceso paralelo concurrente

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 problemas. En primer lugar, la definición de la semántica de las operaciones individuales ya no es obvia. Por ejemplo, si dos procesos quieren extraer el elemento con la prioridad más alta, ¿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 conduce a la contención.

Se inserta el nodo 3 y se establece el puntero del nodo 2 en el nodo 3. Inmediatamente después, se elimina el nodo 2 y se establece el puntero del nodo 1 en el nodo 4. Ahora el nodo 3 ya no es accesible.

El acceso concurrente a una cola de prioridad se puede implementar en un modelo PRAM de lectura concurrente, escritura concurrente (CRCW). A continuación, la cola de prioridad se implementa como una lista de omisión . [25] [26] Además, se utiliza una primitiva de sincronización atómica, CAS , para hacer que la lista de omisión esté libre de bloqueos . Los nodos de la lista de omisión consisten en una clave única, una prioridad, una matriz 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 a la eliminación de manera apropiada.

  • insert(e) : Primero, se crea un nuevo nodo con una clave y una prioridad. Además, se le asigna al nodo una cantidad de niveles, 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 saltos se recorre hasta el nivel más bajo hasta que se encuentra la posición correcta. Durante la búsqueda, para cada nivel, el último nodo recorrido se guardará como nodo padre 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 el nodo sucesor del nuevo nodo en ese nivel. Después, para cada nivel del nuevo nodo, los punteros del nodo padre 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 omisiones hasta llegar a un nodo cuya marca de eliminación no esté establecida. Luego, esta marca de eliminación se establece como verdadera 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. [25] Existe el riesgo de que el nuevo nodo se agregue a la lista de omisiones, pero ya no sea accesible. ( Ver imagen )

K-operaciones con elementos

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. a {\textstyle k} a {\textstyle k}

En un entorno de memoria compartida , la cola de prioridad paralela se puede implementar fácilmente utilizando árboles de búsqueda binarios paralelos y algoritmos de árboles basados ​​en uniones . En particular, k_extract-min corresponde a una división en el árbol de búsqueda binario 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 la clave, k_insert tiene un costo. De lo contrario, primero debemos ordenar el lote, por lo que el costo será . Otras operaciones para la cola de prioridad se pueden aplicar de manera similar. Por ejemplo, k_decrease-key se puede realizar aplicando primero difference y luego union , que primero elimina los elementos y luego los vuelve a insertar con las claves actualizadas. Todas estas operaciones son altamente paralelas, y la eficiencia teórica y práctica se puede encontrar en artículos de investigación relacionados. [27] [28] Oh ( registro ⁡ norte ) {\textstyle O(\log n)} a {\textstyle k} Oh ( a registro ⁡ ( 1 + norte a ) ) {\textstyle O(k\log(1+{\frac {n}{k}}))} Oh ( a registro ⁡ ( 1 + norte a ) + a registro ⁡ a ) = Oh ( a registro ⁡ norte ) {\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 de manera aleatoria uniforme a los procesadores que insertan los elementos en sus colas locales. Nótese que aún se pueden insertar elementos individuales en la cola. Al utilizar esta estrategia, los elementos globales más pequeños se encuentran en la unión de los elementos locales más pequeños de cada procesador con alta probabilidad. Por lo 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 se recopilan en un conjunto de resultados. Los elementos del conjunto de resultados aún están asociados con su procesador original. La cantidad de elementos que se eliminan de cada cola local depende de y la cantidad de procesadores . [29] Mediante la selección paralela, se determinan los elementos más pequeños del conjunto de resultados. Con alta probabilidad, estos son los elementos globales más pequeños. Si no, 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 se pueden devolver estos elementos. Todos los demás elementos del conjunto de resultados se insertan nuevamente en sus colas locales. El tiempo de ejecución de k_extract-min es esperado , donde y es el tamaño de la cola de prioridad. [29] metro {\textstyle m} metro {\textstyle m} a {\textstyle k} pag {\textstyle p} a {\textstyle k} a {\textstyle k} metro {\textstyle m} a {\textstyle k} a {\textstyle k} Oh ( a pag registro ⁡ ( norte ) ) {\textstyle O({\frac {k}{p}}\log(n))} a = Ohmio ( pag ⋅ registro ⁡ ( pag ) ) {\textstyle k=\Omega (p\cdot \log(p))} norte {\textstyle n}

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

Al eliminar varios elementos a la vez, se puede lograr una aceleración considerable. Pero no todos los algoritmos pueden usar 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 menor distancia de la cola de prioridad y calcula nuevas distancias para todos sus nodos vecinos. Si se eliminaran nodos, trabajar en un nodo podría cambiar la distancia de otro de los nodos. Por lo tanto, el uso de operaciones de k elementos destruye la propiedad de configuración de etiquetas del algoritmo de Dijkstra. a {\textstyle k} a {\textstyle k}

Véase también

Referencias

  1. ^ 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.
  2. ^ Skiena, Steven (2010). Manual de diseño de algoritmos (2.ª edición). Springer Science+Business Media . ISBN 978-1-849-96720-4.
  3. ^ P. van Emde Boas. Preservación del orden en un bosque en un tiempo menor que el logarítmico. En Actas del 16.º Simposio Anual sobre Fundamentos de la Ciencia de la Computación , páginas 75-84. IEEE Computer Society, 1975.
  4. ^ Michael L. Fredman y Dan E. Willard. Superando el límite teórico de la información con árboles de fusión. Journal of Computer and System Sciences , 48(3):533-551, 1994
  5. ^ 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.
  6. ^ abc Sleator, Daniel Dominic ; Tarjan, Robert Endre (febrero de 1986). "Montones autoajustables". Revista SIAM de informática . 15 (1): 52–69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN  0097-5397. 
  7. ^ ab Tarjan, Robert (1983). "3.3. Montones de izquierdas". Estructuras de datos y algoritmos de red . págs. 38-42. doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
  8. ^ Hayward, Ryan; McDiarmid, Colin (1991). "Análisis de caso promedio de construcción de montículos mediante inserción repetida" (PDF) . J. Algorithms . 12 : 126–153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Archivado desde el original (PDF) el 2016-02-05 . Consultado el 2016-01-28 . 
  9. ^ "Pila binomial | Wiki de matemáticas y ciencias brillante". brilliant.org . Consultado el 30 de septiembre de 2019 .
  10. ^ ab 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
  11. ^ Okasaki, Chris (1998). "10.2. Abstracción estructural". Estructuras de datos puramente funcionales (1.ª ed.). pp. 158-162. ISBN 9780521631242.
  12. ^ Takaoka, Tadao (1999), Teoría de 2-3 montones (PDF) , pág. 12
  13. ^ Iacono, John (2000), "Límites superiores mejorados para emparejar montones", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF) , Apuntes de clase en 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
  14. ^ Fredman, Michael Lawrence (julio de 1999). "Sobre la eficiencia de emparejar montones y estructuras de datos relacionadas" (PDF) . Revista de la Asociación de Maquinaria Computacional . 46 (4): 473–501. doi :10.1145/320211.320214.
  15. ^ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF) . FOCS '05 Actas del 46.º Simposio anual IEEE sobre fundamentos de la informática. pp. 174–183. CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN .  0-7695-2468-0.
  16. ^ 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.
  17. ^ 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 Computacional . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874. 
  18. ^ Brodal, Gerth Stølting ; Lagogiannis, George; Tarjan, Robert E. (2012). Montones de Fibonacci estrictos (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.
  19. ^ Brodal, Gerth S. (1996), "Colas de prioridad eficientes en el peor de los casos" (PDF) , Actas del 7.º Simposio anual ACM-SIAM sobre algoritmos discretos , págs. 52-58
  20. ^ Goodrich, Michael T .; Tamassia, Roberto (2004). "7.3.6. Construcción de montículos ascendentes". Estructuras de datos y algoritmos en Java (3.ª ed.). págs. 338–341. ISBN 0-471-46983-1.
  21. ^ Thorup, Mikkel (2007). "Equivalencia entre colas de prioridad y ordenación". Revista de la ACM . 54 (6): 28. doi :10.1145/1314690.1314692. S2CID  11494634.
  22. ^ "Copia archivada" (PDF) . Archivado (PDF) desde el original el 20 de julio de 2011 . Consultado el 10 de febrero de 2011 .{{cite web}}: CS1 maint: copia archivada como título ( enlace )
  23. ^ 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 un nuevo borde para agregar al árbol formado por los bordes en A".
  24. ^ "El algoritmo de Prim". Geek para geeks. 18 de noviembre de 2012. Archivado desde el original el 9 de septiembre de 2014 . Consultado el 12 de septiembre de 2014 .
  25. ^ ab Sundell, Håkan; Tsigas, Philippas (2005). "Colas de prioridad concurrentes rápidas y sin bloqueos para sistemas multihilo". Journal of Parallel and Distributed Computing . 65 (5): 609–627. CiteSeerX 10.1.1.67.1310 . doi :10.1109/IPDPS.2003.1213189. S2CID  20995116. 
  26. ^ Lindén, Jonsson (2013), "Una cola de prioridad concurrente basada en listas de saltos con contención de memoria mínima", Informe técnico 2018-003 (en alemán)
  27. ^ Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Simposio sobre algoritmos y arquitecturas paralelas, Actas del 28.º Simposio de la ACM sobre algoritmos y arquitecturas paralelas (SPAA 2016) , ACM, págs. 253–264, arXiv : 1602.02120 , doi : 10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, Número de identificación del sujeto  2897793
  28. ^ Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2018), "PAM: mapas aumentados paralelos", Actas del 23.º Simposio SIGPLAN de la ACM sobre principios y prácticas de programación paralela , ACM, págs. 290-304
  29. ^ ab Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Algoritmos secuenciales y paralelos y estructuras de datos: la caja de herramientas básica . Springer International Publishing. págs. 226–229. doi :10.1007/978-3-030-25209-0. ISBN 978-3-030-25208-3.S2CID201692657  .​

Lectura adicional

  • Referencia de C++ para std::priority_queue
  • Descripciones de Lee Killough
  • libpqueue es una implementación de cola de prioridad genérica (montón) (en C) utilizada por el proyecto Apache HTTP Server.
  • Estudio de las estructuras de colas de prioridad conocidas por Stefan Xenos
  • UC Berkeley - Ciencias de la Computación 61B - Clase 24: Colas de prioridad (video) - Introducción a las colas de prioridad utilizando el montón binario
Obtenido de "https://es.wikipedia.org/w/index.php?title=Cola_de_prioridad&oldid=1251010418"