Imagine um conjunto S de números. Os elementos de S são às vezes chamados chaves ou prioridades (especialmente se há outros dados associados a cada elemento de S). Uma fila-com-prioridades (ou fila priorizada, ou priority queue) é um tipo abstrato de dados que permite executar as seguintes operações sobre S:
Há uma variante dessa definição em que máximo
é substituído por mínimo
.
Para distinguir uma variante da outra,
diremos que a primeira é uma fila-com-prioridades decrescente
(ou de máximo
)
e a segunda é uma fila-com-prioridades crescente
(ou de mínimo
).
Filas-com-prioridades (crescentes e descrescentes) têm um papel fundamental na implementação eficiente de diversos algoritmos célebres, como o algoritmo Heapsort, o algoritmo de Dijkstra, o algoritmo de Prim, e o algoritmo de Huffman.
Esta página é inspirada na seção 6.5 de CLRS.
Não é difícil imaginar maneiras de implementar uma fila-com-prioridades. Nas implementações mais óbvias, algumas das operações ficam rápidas mas as outras ficam lentas. O desafio é inventar uma implementação em que todas as operações sejam rápidas.
No que segue, trataremos de filas-com-prioridades decrescentes, mas é fácil adaptar toda a discussão às filas crescentes.
Eis uma maneira muito eficiente de implementar uma fila-com-prioridades decrescente: mantenha o conjunto S de chaves em um max-heap. Vamos mostrar a seguir como cada uma das operações da fila-com-prioridades decrescente é executada. Suporemos que o max-heap fica armazenado em um vetor A[1 .. n].
É fácil encontrar (e devolver) o valor de um elemento máximo do max-heap A[1 .. n] não vazio (ou seja, com n ≥ 1):
| Encontra-Máximo (A, n) |
| 1 . devolva A[1] |
O seguinte algoritmo remove um elemento máximo do max-heap não vazio A[1 .. n] e devolve o valor desse elemento:
| Extraia-Max (A, n) |
| 1 . max := A[1] |
| 2 . A[1] := A[n] |
| 3 . n := n−1 |
| 4 . Corrige-Descendo (A, n, 1) |
| 5 . devolva max |
O algoritmo Corrige-Descendo foi discutido na página A estrutura heap.
O algoritmo abaixo insere um número c no max-heap A[1 .. n] (ou seja, acrescenta um novo elemento, com valor c, ao vetor) e rearranja o vetor para que ele volte a ser um max-heap:
| Insere-na-Fila (A, n, c) |
| 1 . A[n+1] := c |
| 2 . Corrige-Subindo (A, n+1) |
O algoritmo Corrige-Subindo foi discutido na página A estrutura heap.
O algoritmo seguinte recebe um max-heap não vazio A[1 .. n], um índice i no intervalo 1 .. n e um número c ≥ A[i]. O algoritmo altera para c o valor de A[i] e rearranja o vetor para que ele volte a ser um max-heap:
| Aumenta-Chave (A, i, c) |
| 1 . A[i] := c |
| 2 . Corrige-Subindo (A, i) |
O algoritmo abaixo recebe um max-heap não vazio A[1 .. n], um índice i no intervalo 1 .. n e um número c ≤ A[i]. O algoritmo altera para c o valor de A[i] e rearranja o vetor para que ele volte a ser um max-heap:
| Diminua-Chave (A, n, i, c) |
| 1 . A[i] := c |
| 2 . Corrige-Descendo (A, n, i) |
Para transformar um vetor arbitrário A[1 .. n] em max-heap (de maneira muito eficiente), use o algoritmo Constrói-Max-Heap, já discutido na página A estrutura heap.
Os algoritmos acima são todos muito rápidos: no pior caso, cada um consome tempo proporcional à altura do heap. Como a altura é ⌊lg n⌋ o consumo de tempo está em Ο(lg n) no pior caso.
de mínimo
vetorpor
lista encadeadaou por
arquivose desejar.) Digamos que cada Ai tem ti elementos. Queremos imprimir todos os t = t1 + t2 + … + tn números, em ordem decrescente. Dê um algoritmo que consuma tempo Ο(t lg n) para fazer o serviço. (Faz sentido dizer que o consumo de seu algoritmo está em Ο(n lg n)? Faz sentido dizer que está em Ο(t lg t)?)
Em geral, os elementos do vetor A são objetos arbitrários. Um dos atributos de cada objeto é um número que chamaremos chave (= key). O valor da chave determina a prioridade do objeto na fila. Na descrição acima, para simplificar, cada objeto consiste na chave e nada mais.