Filas de prioridades

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 é 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 de prioridades decrescente (ou de máximo) e a segunda é uma fila de prioridades crescente (ou de mínimo).

Filas de 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.

Implementação eficiente de filas de prioridades

Não é difícil imaginar maneiras de implementar uma fila de prioridades. Infelizmente, nas implementações mais óbvias, alguma das operações fica rápida mas as outras ficam lentas.  O desafio está em inventar uma implementação em que todas as operações sejam rápidas.

Trataremos no que segue de filas de prioridades decrescentes, mas é fácil adaptar toda a discussão às filas crescentes.

Exercícios

  1. Discuta a implementação de uma fila de prioridades decrescente num vetor que armazena as chaves em ordem arbitrária.
  2. Discuta a implementação de uma fila de prioridades decrescente num vetor que armazena as chaves em ordem crescente.

Implementação em heap

Uma maneira muito eficiente de implementar uma fila de prioridades decrescente consiste em manter o conjunto S de chaves em um max-heap.  Vamos mostrar a seguir como cada uma das operações da fila de prioridades decrescente é executada supondo sempre que o max-heap fica armazenado em um vetor A[1..n].

Máximo

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)
_ devolva  A[1]

Remoção de máximo

O seguinte algoritmo 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)
_ maxA[1]
_ A[1] ← A[n]
_ nn−1
_ Corrige-Descendo (A, n, 1)
_ devolva  max

O algoritmo Corrige-Descendo foi discutido quando estudamos a estrutura heap.

Inserção

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)
_ A[n+1] ← c
_ Corrige-Subindo (A, n+1)

O algoritmo Corrige-Subindo foi discutido quando estudamos a estrutura heap.

Aumento do valor de uma chave

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)
_ A[i] ← c
_ Corrige-Subindo (A, i)

Redução do valor de uma chave

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)
_ A[i] ← c
_ Corrige-Descendo (A, n, i)

Consumo de tempo

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.

Exercícios

  1. Prove que os algoritmos Encontra-Máximo, Extrai-Máximo, Insere-na-Fila, Aumenta-Chave e Diminui-Chave estão corretos.
  2. [CLRS 6.5-7]  Escreva uma implementação eficiente da operação Remove com parâmetros (A, n, i). Ela deve remover o nó i do max-heap A[1..n] e armazenar os elementos restantes, em forma de max-heap, no vetor A[1..n−1].
  3. Reescreva o código do algoritmo Heapsort usando as operações de manipulação de heap definidas acima.
  4. Escreva implementações para as operações sobre uma fila de prioridades, que encontra um elemento mínimo da fila, extrai um elemento mínimo da fila, etc.
  5. Escreva um algoritmo que receba um max-heap A[1..n] e um número x e devolva um índice i tal que A[i] = x ou devolva 0 se tal i não existe.  Procure escrever um algoritmo eficiente.  Qual o consumo de tempo do seu algoritmo?
  6. [CLRS 6.5-8]  Suponha dado um conjunto A1, A2, …, An de vetores numéricos crescentes.  (Você pode trocar vetor por lista encadeada ou por arquivo se 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 do seu algoritmo está em Ο(n lg n)?   Faz sentido dizer que está em Ο(t lg t)?)  (Compare com exercício semelhante na página sobre códigos de Huffman.) 

Objetos e chaves

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 prioridade na fila.  Na descrição acima, cada objeto consiste na chave e nada mais.


Valid HTML 4.01 Strict Valid CSS!