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. A cola de prioridade serve primeiro os elementos de maior prioridade. 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.
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:
Cola de prioridade máxima insert(S, elemento, prioridade): 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 ou extract). 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): 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 ou extract). 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 e extract_max, custo . 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] > queue[highest]: highest = i return queue.pop(highest)
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 e extract_max en tempo .
def insert_ordered(queue, element, priority): i = len(queue) while i > 0 and queue[i - 1] > priority: i -= 1 queue.insert(i, (priority, element))
def extract_max_ordered(queue): if not queue: raise IndexError("cola baleira") return queue.pop()
Implementación habitual Para mellorar o rendemento, as colas de prioridade adoitan basearse nun montículo, o que dá para insercións e extraccións e para construír o montículo inicialmente a partir de elementos. Variantes como os montículos de emparellamento ou os montículos de Fibonacci poden dar mellores cotas para algunhas operacións. Terceira edición, p. 518.
Alternativamente, cunha árbore binaria de busca auto-equilibrada a inserción e a extracción tamén levan , aínda que construír a árbore a partir dunha secuencia de elementos leva . 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 é . 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 listas ligadas máis un punteiro . Inserir un elemento de chave engádeo á -ésima lista e actualiza , ambas as dúas cousas en tempo constante. extract-min elimina e devolve un elemento da lista de índice e incrementa segundo cómpre; isto leva no peor caso. Estas colas son útiles para ordenar os vértices dun grafo polo seu grao. Unha árbore de van Emde Boas admite inserción, borrado e busca de predecesor ou sucesor en , e consulta do mínimo e máximo en . A representación directa reserva espazo, que é para un universo de chaves de bits. As variantes con hashing poden reducir ese custo.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. A árbore de fusión de Fredman e Willard implementa minimum en tempo e insert e extract-min en . 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».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.
Para aplicacións que fan moitas operacións de «vista» (peek) por cada extract-min, a complexidade das vistas pódese reducir a 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 Smoothsort Montículo de Leonardo Ordenación por selección Vector desordenado Ordenación por inserción Vector ordenado Tree sort árbore binaria de busca auto-equilibrada
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: Presentamos unha redución determinista de espazo linear xeral das colas de prioridade á ordenación, que implica que se podemos ordenar ata chaves en tempo por chave, entón existe unha cola de prioridade que admite delete e insert en tempo 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 , mentres que a inserción e o borrado custan . A extracción inclúe un borrado e non debe confundirse coa consulta sen modificación. Por exemplo, unha ordenación de custo conduce a cotas para inserción e extracción, e para consultar o mínimo.
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