Cola de prioridade

Fontes e ligazóns
Freebase
Freebase	/m/063rk
MathWorld	PriorityQueue
OpenAlex	C26951474

	Subclase de cola
	Uso priorización
	Medio usado Montículo

Cola de prioridade
	Subclase de cola
	Uso priorización
	Medio usado Montículo
Freebase
Fontes e ligazóns
Freebase
Freebase	/m/063rk
MathWorld	PriorityQueue
OpenAlex	C26951474
	Wikidata

En ciencias da computación, unha cola de prioridade é un tipo de dato abstracto semellante a unha cola normal na que cada elemento ten unha prioridade asociada que determina a súa orde de servizo.^[1] A cola de prioridade serve primeiro os elementos de maior prioridade.^[1] Os valores de prioridade deben ser instancias dun tipo de dato ordenado, e pódese dar maior prioridade aos valores menores ou aos maiores segundo a relación de orde dada. Por exemplo, na biblioteca estándar de Java, a clase PriorityQueue considera que o elemento menor respecto da súa orde ten a maior prioridade.^[2]

Aínda que as colas de prioridade se implementan a miúdo con montículos, son conceptualmente distintos. Unha cola de prioridade pódese implementar cun montículo ou con outros métodos, do mesmo xeito que unha lista se pode implementar cunha lista ligada ou cun vector.

Operacións

Unha cola de prioridade ten as seguintes operacións:^[3]^[4]^[5]

Cola de prioridade máxima

insert(S, elemento, prioridade):^[4]^[5] engadir un elemento ao conxunto S cunha prioridade asociada.
maximum(S): devolver o elemento de maior prioridade (tamén find_max).
extract_max(S): retirar do conxunto S o elemento de maior prioridade e devolvelo (tamén delete^[4] ou extract^[5]).
increase_key(S, elemento, k): aumentar a prioridade asociada a un elemento ata o novo valor k.

Cola de prioridade mínima

insert(S, elemento, prioridade):^[4]^[5] engadir un elemento ao conxunto S cunha prioridade asociada.
minimum(S): devolver o elemento de menor prioridade (tamén find_min).
extract_min(S): retirar do conxunto S o elemento de menor prioridade e devolvelo (tamén delete^[4] ou extract^[5]).
decrease_key(S, elemento, k): diminuír a prioridade asociada a un elemento ata o novo valor k.

As pilas e as colas pódense implementar como casos particulares de colas de prioridade, coa prioridade determinada pola orde de inserción. Nunha pila, a prioridade de cada elemento inserido é monótona crecente; así, o último elemento inserido é sempre o primeiro en saír. Nunha cola, a prioridade é monótona decrecente; así, o primeiro elemento inserido é o primeiro en saír.

Nalgunhas implementacións, se dous elementos teñen a mesma prioridade, sérvense na orde en que se encolaron. Noutras, a orde dos elementos coa mesma prioridade non está definida.

Implementación

Implementacións simples

Pódese crear unha cola de prioridade simple, pero ineficiente, de varias formas; serven para amosar o comportamento esperado dun xeito máis sinxelo.

Inserir os elementos nun vector desordenado; atopar e extraer o de maior prioridade.
Nun vector dinámico, insert ten custo amortizado $O(1)$ e extract_max, custo $O(n)$ . Un exemplo en Python, con pares (prioridade, elemento), é:

def insert_unordered(queue, element, priority):
    queue.append((priority, element))

def extract_max_unordered(queue):
    if not queue:
        raise IndexError("cola baleira")
    highest = 0
    for i in range(1, len(queue)):
        if queue[i][0] > queue[highest][0]:
            highest = i
    return queue.pop(highest)[1]

Inserir os elementos nun vector ordenado de menor a maior prioridade; extraer o último, evitando desprazar os demais.
A operación insert faise en tempo $O(n)$ e extract_max en tempo $O(1)$ .

def insert_ordered(queue, element, priority):
    i = len(queue)
    while i > 0 and queue[i - 1][0] > priority:
        i -= 1
    queue.insert(i, (priority, element))

def extract_max_ordered(queue):
    if not queue:
        raise IndexError("cola baleira")
    return queue.pop()[1]

Implementación habitual

Para mellorar o rendemento, as colas de prioridade adoitan basearse nun montículo, o que dá $O(\log n)$ para insercións e extraccións e $O(n)$ para construír o montículo inicialmente a partir de $n$ elementos. Variantes como os montículos de emparellamento ou os montículos de Fibonacci poden dar mellores cotas para algunhas operacións.^[6]

Alternativamente, cunha árbore binaria de busca auto-equilibrada a inserción e a extracción tamén levan $O(\log n)$ , aínda que construír a árbore a partir dunha secuencia de elementos leva $O(n\log n)$ . Desde o punto de vista do espazo, usar unha árbore de busca auto-equilibrada cunha lista ligada consome máis almacenamento, porque require gardar referencias adicionais.

Desde o punto de vista da complexidade computacional, as colas de prioridade son congruentes cos algoritmos de ordenación: os algoritmos de ordenación eficientes permiten crear colas de prioridade eficientes.

Montículos especializados

Existen varios montículos especializados que fornecen operacións adicionais ou superan as implementacións baseadas en montículo para tipos concretos de chaves, en particular chaves enteiras. Supoñamos que o conxunto de chaves posibles é $\{1,2,...,C\}$ .

Cando só se necesitan insert, find-min e extract-min con prioridades enteiras, pódese construír unha cola de cubos como un vector de $C$ listas ligadas máis un punteiro ${\text{top}}$ . Inserir un elemento de chave $k$ engádeo á $k$ -ésima lista e actualiza ${\text{top}}$ , ambas as dúas cousas en tempo constante. extract-min elimina e devolve un elemento da lista de índice ${\text{top}}$ e incrementa ${\text{top}}$ segundo cómpre; isto leva $O(C)$ no peor caso. Estas colas son útiles para ordenar os vértices dun grafo polo seu grao.^[7]^:374
Unha árbore de van Emde Boas admite inserción, borrado e busca de predecesor ou sucesor en $O(\log \log C)$ , e consulta do mínimo e máximo en $O(1)$ . A representación directa reserva $O(C)$ espazo, que é $O(2^{m})$ para un universo de chaves de $m$ bits. As variantes con hashing poden reducir ese custo.^[8]
A árbore de fusión de Fredman e Willard implementa minimum en tempo $O(1)$ e insert e extract-min en $O(\log n/\log \log C)$ . Con todo, os propios autores sinalan que «os nosos algoritmos teñen só interese teórico; os factores constantes impiden a súa aplicación práctica».^[9]

Para aplicacións que fan moitas operacións de «vista» (peek) por cada extract-min, a complexidade das vistas pódese reducir a $O(1)$ gardando o elemento de maior prioridade tras cada inserción e extracción.

As colas de prioridade monótonas son colas especializadas que se optimizan para o caso no que nunca se insire un elemento de prioridade menor ca un xa extraído.

Equivalencia entre colas de prioridade e algoritmos de ordenación

Usar unha cola de prioridade para ordenar

A semántica das colas de prioridade suxire de forma natural un método de ordenación: inserir todos os elementos nunha cola de prioridade e retiralos secuencialmente; sairán en orde. Este método é equivalente aos algoritmos de ordenación seguintes segundo a implementación da cola de prioridade:

Nome	Implementación da cola	Mellor	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$
Ordenación por selección	Vector desordenado	$n^{2}$	$n^{2}$	$n^{2}$
Ordenación por inserción	Vector ordenado	$n$	$n^{2}$	$n^{2}$
Tree sort	árbore binaria de busca auto-equilibrada	$n\log n$	$n\log n$	$n\log n$

Usar un algoritmo de ordenación para facer unha cola de prioridade

Un algoritmo de ordenación tamén se pode usar para implementar unha cola de prioridade. En concreto, Thorup demostrou:^[10]

Presentamos unha redución determinista de espazo linear xeral das colas de prioridade á ordenación, que implica que se podemos ordenar ata $n$ chaves en tempo $S(n)$ por chave, entón existe unha cola de prioridade que admite `delete` e `insert` en tempo $O(S(n))$ e `find-min` en tempo constante. (tradución do inglés)

Nas condicións desa redución, a consulta do mínimo (find-min) custa $O(1)$ , mentres que a inserción e o borrado custan $O(S(n))$ . A extracción inclúe un borrado e non debe confundirse coa consulta sen modificación. Por exemplo, unha ordenación de custo $O(n\log n)$ conduce a cotas $O(\log n)$ para inserción e extracción, e $O(1)$ para consultar o mínimo.^[11]

Bibliotecas

Unha cola de prioridade considérase a miúdo unha «estrutura de datos contedor».

A Standard Template Library (STL) de C++ inclúe std::priority_queue, un adaptador de contedor. Os seus tres parámetros de modelo son o tipo de elemento T, o contedor subxacente (por defecto std::vector<T>) e o comparador (por defecto std::less<T>). Este último dá lugar a unha cola máxima. Algúns construtores aceptan dous iteradores para inicializar a cola cun rango, pero eses iteradores non son parámetros do modelo. A interface non permite percorrer directamente os elementos. As bibliotecas Boost tamén ofrecen colas de prioridade na súa biblioteca de montículos.

O módulo heapq de Python implementa un montículo mínimo binario sobre unha lista.

A biblioteca de Java contén a clase java.util.PriorityQueue, que implementa unha cola de prioridade mínima como montículo binario.

A biblioteca de .NET contén a clase System.Collections.Generic.PriorityQueue, que implementa un montículo mínimo cuaternario.

A biblioteca de Scala contén a clase scala.collection.mutable.PriorityQueue, que implementa unha cola de prioridade máxima.

A biblioteca de Go contén o módulo container/heap, que implementa un montículo mínimo sobre calquera estrutura compatible.

A biblioteca estándar de Rust contén a estrutura std::collections::BinaryHeap, que implementa unha cola de prioridade cun montículo binario.

A extensión Standard PHP Library contén a clase SplPriorityQueue.

O marco Core Foundation de Apple contén a estrutura CFBinaryHeap, que implementa un montículo mínimo.

Aplicacións

Xestión de ancho de banda

A cola de prioridade pódese usar para xestionar recursos limitados como o ancho de banda nunha liña de transmisión dun router. Se hai tráfico de saída encolado por falta de ancho de banda, todas as demais colas pódense deter para enviar o tráfico da cola de maior prioridade en canto chegue. Isto garante que o tráfico prioritario (como o tráfico en tempo real, por exemplo un fluxo RTP dunha conexión VoIP) se reenvíe co menor atraso posible. Moitos protocolos modernos de rede de área local tamén inclúen o concepto de colas de prioridade na subcapa de control de acceso ao medio (MAC), como IEEE 802.11e e ITU-T G.hn.

Normalmente establécese un limitador para restringir o ancho de banda que pode ocupar a cola de maior prioridade, evitando así que os paquetes prioritarios afoguen o resto do tráfico.

Simulación de eventos discretos

Outro uso é xestionar os eventos nunha simulación de eventos discretos. Os eventos engádense á cola co seu tempo de simulación como prioridade. A execución da simulación procede retirando repetidamente a cima da cola e executando o evento correspondente.

Algoritmo de Dijkstra

Cando o grafo se almacena como lista de adxacencia ou matriz, pódese usar unha cola de prioridade para extraer o mínimo de forma eficiente ao implementar o algoritmo de Dijkstra, aínda que tamén se necesita poder alterar eficientemente a prioridade dun vértice. Se o grafo se almacena como obxectos de nó e os pares prioridade-nó se insiren nun montículo, non é necesario alterar a prioridade se se levan a conta dos nós visitados.

Codificación de Huffman

A codificación de Huffman require obter repetidamente as dúas árbores de menor frecuencia; unha cola de prioridade é un dos métodos para facelo.

Algoritmos de busca best-first

Os algoritmos de busca best-first empregan unha cola de prioridade para explorar primeiro as rutas máis prometedoras. No algoritmo A*, a prioridade combina o custo acumulado cunha estimación do custo restante. A optimalidade depende das condicións da heurística e da xestión das reaperturas de nós; non é unha propiedade de toda busca best-first.

Algoritmo de triangulación ROAM

O algoritmo ROAM calcula unha triangulación que cambia dinamicamente dun terreo, dividindo os triángulos onde se necesita máis detalle e fusionándoos onde se necesita menos. Usa dúas colas de prioridade: unha para os triángulos que se poden dividir e outra para os que se poden fusionar.

Algoritmo de Prim

Usando unha cola de prioridade de montículo mínimo no algoritmo de Prim para atopar a árbore de expansión mínima dun grafo conexo e non dirixido, acádase un bo tempo de execución. Nesta implementación, o peso das arestas úsase para decidir a prioridade dos vértices: a menor peso, maior prioridade.^[12]

Cola de prioridade en paralelo

A paralelización pode acelerar as colas de prioridade, pero require cambios na interface. Unha actualización secuencial adoita ter un custo $O(1)$ ou $O(\log n)$ , polo que non hai ganancia práctica en paralelizar esa operación. Un cambio posible é permitir o acceso concorrente de varios procesadores á mesma cola de prioridade; outra é permitir operacións por lotes que traballen con $k$ elementos no canto dun só.

Acceso paralelo concorrente

Se a cola permite acceso concorrente, varios procesos poden operar sobre ela á vez, o que expón dous problemas: a semántica de cada operación xa non é obvia e o acceso compartido xera contención.^[13]

O acceso concorrente a unha cola de prioridade pódese implementar sobre un modelo PRAM CRCW (lectura e escritura concorrentes) cunha skip list.^[13] Ademais, úsase a primitiva atómica compare-and-swap (CAS) para facer a skip list libre de bloqueos. Os nós da skip list constan dunha chave única, unha prioridade, un vector de punteiros para cada nivel e unha marca de borrado.

insert(e): primeiro créase un novo nó cunha chave e unha prioridade, e asígnaselle un número de niveis. Logo faise unha busca para atopar a posición correcta e actualízanse os punteiros correspondentes.
extract-min: percorre a skip list ata chegar a un nó cuxa marca de borrado non estea posta, márcao como borrado e actualiza os punteiros dos seus nós pais.

Se se permite o acceso concorrente, poden xurdir conflitos entre dous procesos; por exemplo, se un proceso insire un novo nó mentres outro está a borrar o seu predecesor, o novo nó pode quedar inalcanzable.

Operacións de $k$ elementos

Neste contexto, as operacións xeneralízanse a lotes de $k$ elementos. Nun contorno de memoria compartida, a cola pode usar árbores binarias de busca paralelas e algoritmos de árbores baseados en Join. Nunha árbore aumentada con tamaños, separar os $k$ elementos menores pode facerse cun split de custo $O(\log n)$ ; enumerar os elementos separados require ademais $O(k)$ . A inserción dun lote relaciónase cunha operación union.^[14]^[15]

O resto da sección trata un algoritmo de memoria distribuída, onde cada procesador ten a súa propia memoria e unha cola de prioridade local, e os elementos da cola global distribúense entre os procesadores. Ao extraer, retíranse os elementos menores de cada cola local a un conxunto de resultados e determínanse por selección paralela os $k$ menores globais. Ao eliminar varios elementos á vez pódese acadar unha aceleración considerable, pero a extracción arbitraria dos $k$ menores non conserva a orde de procesamento que require o algoritmo secuencial clásico de Dijkstra: relaxar as arestas dun dos nós extraídos pode reducir a distancia tentativa doutro. Isto non impide deseñar variantes paralelas de camiños máis curtos, como Δ-stepping.^[16]^[17]

Notas

1 2 Miller Jr., Robert G. (1960). "Priority queues" (PDF). The Annals of Mathematical Statistics (en inglés) (Stanford University) 31: 86–103. doi:10.1214/aoms/1177705990.
↑ "PriorityQueue (Java SE 9 & JDK 9 )". docs.oracle.com (en inglés).
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "6.5: Priority queues". Introduction to Algorithms (en inglés) (2.ª ed.). MIT Press. pp. 138–142.
1 2 3 4 5 Rönngren, Robert; Ayani, Rassul (1 de abril de 1997). "A comparative study of parallel and sequential priority queue algorithms". ACM Trans. Model. Comput. Simul. (en inglés) 7 (2): 157–209. ISSN 1049-3301. doi:10.1145/249204.249205.
1 2 3 4 5 Ayani, R. (decembro de 1990). "LR-algorithm: Concurrent operations on priority queues". Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing 1990 (en inglés). pp. 22–25. ISBN 0-8186-2087-0. doi:10.1109/SPDP.1990.143500.
↑ "Chapter 20: Fibonacci Heaps". Introduction to Algorithms (en inglés) (2.ª ed.). MIT Press. 2001. pp. 476–497. Terceira edición, p. 518.
↑ Skiena, Steven (2010). The Algorithm Design Manual (en inglés) (2.ª ed.). Springer Science+Business Media. ISBN 978-1-849-96720-4.
↑ P. van Emde Boas. «Preserving order in a forest in less than logarithmic time». En Proceedings of the 16th Annual Symposium on Foundations of Computer Science, páxinas 75–84. IEEE Computer Society, 1975.
↑ Michael L. Fredman e Dan E. Willard. «Surpassing the information theoretic bound with fusion trees». Journal of Computer and System Sciences, 48(3):533–551, 1994.
↑ Thorup, Mikkel (2007). "Equivalence between priority queues and sorting". Journal of the ACM (en inglés) 54 (6): 28. doi:10.1145/1314690.1314692.
↑ "Advanced Data Structures, Lecture 17" (PDF) (en inglés). MIT.
↑ Introduction to Algorithms (en inglés) (3.ª ed.). p. 634.
1 2 Sundell, Håkan; Tsigas, Philippas (2003). "Fast and lock-free concurrent priority queues for multi-thread systems". Proceedings International Parallel and Distributed Processing Symposium (IPDPS 2003) (en inglés). p. 11. ISBN 0-7695-1926-1. doi:10.1109/IPDPS.2003.1213189.
↑ Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016). "Just Join for Parallel Ordered Sets". Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (en inglés). ACM. pp. 253–264. ISBN 978-1-4503-4210-0. arXiv:1602.02120. doi:10.1145/2935764.2935768.
↑ Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2018). "PAM: parallel augmented maps". Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (en inglés). ACM. pp. 290–304.
↑ Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox (en inglés). Springer International Publishing. pp. 226–229. ISBN 978-3-030-25208-3. doi:10.1007/978-3-030-25209-0.
↑ Meyer, Ulrich; Sanders, Peter (2003). "Δ-stepping: a parallelizable shortest path algorithm". Journal of Algorithms (en inglés) 49 (1): 114–152. doi:10.1016/S0196-6774(03)00076-2.

Véxase tamén

Bibliografía

Thomas H. Cormen et al. Introduction to Algorithms, segunda edición, sección 6.5: «Priority queues», páxinas 138–142. (en inglés)

Outros artigos

Ligazóns externas

Referencia de C++ para std::priority_queue (en inglés)
libpqueue, implementación xenérica en C usada polo servidor HTTP Apache (en inglés)
Implementación dunha cola de prioridade en Java (en inglés)

[:0-1] 1 2 Miller Jr., Robert G. (1960). "Priority queues" (PDF). The Annals of Mathematical Statistics (en inglés) (Stanford University) 31: 86–103. doi:10.1214/aoms/1177705990.

[2] "PriorityQueue (Java SE 9 & JDK 9 )". docs.oracle.com (en inglés).

[clrs4-3] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "6.5: Priority queues". Introduction to Algorithms (en inglés) (2.ª ed.). MIT Press. pp. 138–142.

[:1-4] 1 2 3 4 5 Rönngren, Robert; Ayani, Rassul (1 de abril de 1997). "A comparative study of parallel and sequential priority queue algorithms". ACM Trans. Model. Comput. Simul. (en inglés) 7 (2): 157–209. ISSN 1049-3301. doi:10.1145/249204.249205.

[:2-5] 1 2 3 4 5 Ayani, R. (decembro de 1990). "LR-algorithm: Concurrent operations on priority queues". Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing 1990 (en inglés). pp. 22–25. ISBN 0-8186-2087-0. doi:10.1109/SPDP.1990.143500.

[CLRS_priority_queue_pp476-6] "Chapter 20: Fibonacci Heaps". Introduction to Algorithms (en inglés) (2.ª ed.). MIT Press. 2001. pp. 476–497. Terceira edición, p. 518.

[7] Skiena, Steven (2010). The Algorithm Design Manual (en inglés) (2.ª ed.). Springer Science+Business Media. ISBN 978-1-849-96720-4.

[8] P. van Emde Boas. «Preserving order in a forest in less than logarithmic time». En Proceedings of the 16th Annual Symposium on Foundations of Computer Science, páxinas 75–84. IEEE Computer Society, 1975.

[9] Michael L. Fredman e Dan E. Willard. «Surpassing the information theoretic bound with fusion trees». Journal of Computer and System Sciences, 48(3):533–551, 1994.

[10] Thorup, Mikkel (2007). "Equivalence between priority queues and sorting". Journal of the ACM (en inglés) 54 (6): 28. doi:10.1145/1314690.1314692.

[11] "Advanced Data Structures, Lecture 17" (PDF) (en inglés). MIT.

[CLR-12] Introduction to Algorithms (en inglés) (3.ª ed.). p. 634.

[skiplist-13] 1 2 Sundell, Håkan; Tsigas, Philippas (2003). "Fast and lock-free concurrent priority queues for multi-thread systems". Proceedings International Parallel and Distributed Processing Symposium (IPDPS 2003) (en inglés). p. 11. ISBN 0-7695-1926-1. doi:10.1109/IPDPS.2003.1213189.

[join-based-14] Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016). "Just Join for Parallel Ordered Sets". Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (en inglés). ACM. pp. 253–264. ISBN 978-1-4503-4210-0. arXiv:1602.02120. doi:10.1145/2935764.2935768.

[pam-15] Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2018). "PAM: parallel augmented maps". Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (en inglés). ACM. pp. 290–304.

[AlgToolbox-16] Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox (en inglés). Springer International Publishing. pp. 226–229. ISBN 978-3-030-25208-3. doi:10.1007/978-3-030-25209-0.

[17] Meyer, Ulrich; Sanders, Peter (2003). "Δ-stepping: a parallelizable shortest path algorithm". Journal of Algorithms (en inglés) 49 (1): 114–152. doi:10.1016/S0196-6774(03)00076-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]