Esta página é inspirada na seção 6.5 de CLRS, que discute priority queues. Veja também a seção 2.5 de KT e o verbete Priority_queue na Wikipedia. Veja ainda a página de Lee Killough sobre o assunto.
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 de prioridades é uma estrutura de dados que permite executar as seguintes operações sobre S:
de maneira eficiente. Essas operações estão embutidas em diversos algoritmos célebres como, por exemplo, o algoritmo Heapsort, o algoritmo de Dijkstra, o algoritmo de Prim, e o algoritmo de Huffman.
Esta página trata da implementação de uma fila de prioridades em um max-heap A[1..n].
Eis o algoritmo que encontra (e devolve) 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 algoritmo seguinte remove um elemento máximo do max-heap não vazio A[1..n] e devolve o valor desse elemento:
| Extrai-Máximo (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 quando estudamos 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 quando estudamos 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:
| Diminui-Chave (A, n, i, c) |
| 1 _ A[i] ← c |
| 2 _ Corrige-Descendo (A, n, i) |
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⌋ (veja definição de piso), o consumo de tempo está em Ο(lg n) no pior caso.
Em geral, os elementos do vetor A são objetos arbitrários. Um dos atributos desses objetos é um número que chamaremos chave. A chave de cada objeto determina sua a prioridade na fila. (Na descrição acima, cada objeto consiste na chave e nada mais.)