Este capítulo é um resumo de parte das seções 9.1 a 9.4 do livro do Sedgewick. O capítulo
Uma fila de prioridades (= priority queue = PQ) é um tipo abstrato de dados (= ADT) que manipula um conjunto de coisas que chamaremos de itens. Os itens são de qualquer tipo que admita comparações. Usaremos o nome genérico Item para designar esse tipo.
A ideia é que itens de maior valor têm maior prioridade
para sair da fila.
Um item c1 da fila é máximo
se nenhum outro item é maior que c1.
Nada impede que tenhamos dois ou mais itens máximos.
Toda fila de prioridades está sujeita a duas operações básicas:
Queremos implementar a fila de prioridades de modo que ambas as operações básicas sejam rápidas, mesmo no pior caso.
Exemplo: Para tornar os conceitos mais concretos, o programa 9.2 do Sedgewick mostra uma implementação muito simples (e ineficiente) de fila de prioridade. Nessa implementação, a fila reside em um vetor pq[0..N-1].
// A fila de prioridades residirá no // vetor pq[0..N-1]. // Item *pq; int N; // Reserva espaço para uma fila de // prioridades com no máximo maxN itens. // void PQinit0(int maxN) { pq = malloc(maxN * sizeof (Item)); N = 0; } // Devolve 1 se a fila de prioridades // pq[0..N-1] está vazia. Devolve 0 em caso // contrário. // int PQempty0() { return N == 0; } // Insere um item v na fila de prioridades // pq[0..N-1]. Supõe que N < maxN. // void PQinsert0(Item v) { pq[N++] = v; } #define less(A,B) (A < B) #define exch(A,B) {Item t = A; A = B; B = t;} // Remove um item máximo da fila de // prioridades pq[0..N-1]. Supõe que a fila // não está vazia. Devolve o item removido. // Item PQdelmax0() { int max = 0; for (int j = 1; j < N; j++) if (less(pq[max], pq[j])) max = j; exch(pq[max], pq[N-1]); return pq[--N]; }(Os nomes das funções acima terminam em
0para diferenciá-las das funções mais sofisticadas que veremos adiante.)Qual o consumo de tempo dessa implementação de fila de prioridades? Cada operação PQinsert0 consome tempo constante (ou seja, independente do valor de N). Cada operação PQdelmax0 consome tempo proporcional a N.
Um dos exercícios abaixo discute outra implementação muito simples; nela, o vetor pq[0..N-1] é mantido em ordem crescente. O resto do capítulo usa uma terceira implementação, bem mais sofisticada e bem mais eficiente. Antes de tratar dessa implementação é preciso introduzir o conceito de heap.
Um heap é um vetor pq[1..N] (note que o primeiro índice é 1 e não 0) tal que
pq[⌊k/2⌋] ≥ pq[k]
para todo k em 2..N. A expressão ⌊k/2⌋ denota o piso de k/2. Na linguagem C, se a variável k é do tipo int então ⌊k/2⌋ é igual ao valor da expressão k/2, e portanto a condição que define um heap pode ser escrita simplesmente assim:
pq[k/2] ≥ pq[k].
Para enfatizar o ≥
,
podemos dizer que estamos lidando com um max-heap.
Dizemos que o item que está na posição
k/2
é o pai do item que está na posição k.
Por exemplo, o pai de pq[9] é pq[4];
o pai de pq[8] também é pq[4].
Dizemos que os filhos de um item na posição k
são os itens que estão nas posições
2*k e 2*k+1.
Com isso, a definição de max-heap pode ser reformulada da seguinte maneira,
vaga mas sugestiva: todo pai é maior ou igual que cada um de seus filhos.
| 1 | |||||||||||||||||||||||||||||||||||||||||||||||
| 2 | 3 | ||||||||||||||||||||||||||||||||||||||||||||||
| 4 | 5 | 6 | 7 | ||||||||||||||||||||||||||||||||||||||||||||
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||||||||||||||||||||||||||||||||||||||||
| 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | ||||||||||||||||||||||||||||||||
| 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | ||||||||||||||||||||||||
A figura mostra um vetor pq[1..55]. Os números dentro das caixas são os índices. O número de itens em cada camada, exceto talvez no última, é uma potência de 2. O pai de cada item na camada i está na camada i-1. O número de camadas é 1 + lg(55), sendo lg(x) o número ⌊log2 x⌋. Se eu tivesse N no lugar de 55, o número de camadas seria 1 + lg(N).
Os programas 9.3, 9.4 e 9.5 do livro de Sedgewick descrevem uma implementação de uma fila de prioridades que usa a estrutura de dados max-heap.
// A fila de prioridades residirá em um vetor
// pq[1..N]. (Note que o primeiro índice é 1
// e não 0.)
Item *pq;
int N;
void PQinit(int maxN) {
pq = malloc((maxN+1) * sizeof (Item));
N = 0;
}
int PQempty() {
return N == 0;
}
void PQinsert(Item v) {
pq[++N] = v;
fixUp(pq, N);
}
Item PQdelmax() {
exch(pq[1], pq[N]);
fixDown(pq, N-1);
return pq[N--];
}
As funções fixUp e fixDown são o coração dessa implementação:
#define less(A,B) (A < B)
#define exch(A,B) {Item t = A; A = B; B = t;}
// Recebe um vetor a[1..k] tal que a[1..k-1]
// é um max-heap. Rearranja o vetor de modo
// a transformá-lo em um max-heap.
//
void fixUp (Item a[], int k) {
while (k > 1 && less(a[k/2], a[k])) {
exch(a[k], a[k/2]);
k = k/2;
}
}
// Rearranja um vetor a[1..N] de modo a
// transformá-lo em um max-heap. Supõe que
// os "subvetores" cujas "raízes" são os
// índices 2 e 3 já são heaps.
//
void fixDown (Item a[], int N) {
int j, k = 1;
while (2*k <= N) {
j = 2*k;
if (j < N && less(a[j], a[j+1])) j++;
// j é o "maior" dos filhos de k
if (!less(a[k], a[j])) break;
exch(a[k], a[j]);
k = j;
}
}
O consumo de tempo dessa implementação
é proporcional ao número de comparações
entre itens.
Cada operação PQinsert faz no máximo
2 lg(N)
comparações,
pois o heap tem lg(N) camadas
e há 2 comparações para cada mudança de camada
.
Analogamente,
cada operação PQdelmax faz no máximo
2 lg(N)
comparações.
Para uso futuro, convém reescrever a função fixDown de modo que ela seja um pouco mais geral:
// Rearranja o vetor a[1..N] de modo que
// o "subvetor" cuja "raiz" é k seja um
// max-heap. Supõe que já são max-heaps
// os "subvetores" cujas "raízes" são
// os filhos de k.
//
void fixDownG (Item a[], int k, int N) {
int j;
while (2*k <= N) {
j = 2*k;
if (j < N && less(a[j], a[j+1])) j++;
if (!less(a[k], a[j])) break;
exch(a[k], a[j]);
k = j;
}
}
É claro que fixDownG (a, 1, N) é o mesmo que fixDown (a, N).
void xxx (Item a[], int k, int N) {
Item v = a[k];
int j = k;
while (2*k <= N) {
j = 2*k;
if (j < N && less(a[j], a[j+1])) j++;
if (v >= a[j]) break;
a[k] = a[j];
k = j;
}
a[j] = v;
}
O algoritmo Heapsort resolve o seguinte
Problema: Rearranjar um vetor a[p..r] de modo que ele fique em ordem crescente.
O programa 9.6 de Sedgewick descreve uma primeira implementação do algoritmo Heapsort:
// Rearranja um vetor a[p..r] de modo
// que ele fique em ordem crescente.
//
void PQsort (Item a[], int p, int r) {
int k;
PQinit ();
for (k = p; k <= r; k++)
PQinsert (a[k]);
for (k = r; k >= p; k--)
a[k] = PQdelmax ();
}
Essa implementação tem o defeito de usar um vetor adicional
pq[1..r] como rascunho
.
A função abaixo é uma maneira mais profissional
de implementar o algoritmo Heapsort.
A implementação não usa PQinsert nem PQdelmax,
mas apela diretamente para a função fixDownG.
(Com isso, não precisa de espaço adicional de rascunho.)
// Rearranja um vetor a[1..N] de modo
// que ele fique em ordem crescente.
//
void heapsort (Item a[], int N) {
for (int k = N/2; k >= 1; k--)
fixDownG (a, k, N);
while (N > 1) {
exch (a[1], a[N]);
fixDownG (a, 1, --N);
}
}
No início de cada iteração do while, o vetor a está no seguinte estado:
| 1 | N | ||||||||||||
| 888 | 777 | 666 | 555 | 444 | 333 | 222 | 111 | 000 | 997 | 998 | 998 | 998 | 999 |
| max-heap, elementos pequenos | crescente, elementos grandes | ||||||||||||
O programa 9.7 de Sedgewick é uma variante da função heapsort. Ela se aplica a qualquer vetor a[p..r] mesmo que p seja diferente 1. A variável pq contém o endereço de a[p-1]; portanto, pq[1..N] é exatamente o mesmo que a[p..r].
// Rearranja um vetor a[p..r] de modo que
// ele fique em ordem crescente.
//
void heapsort2 (Item a[], int p, int r) {
int N = r - p + 1;
Item *pq = a + p - 1;
for (int k = N/2; k >= 1; k--)
fixDownG (pq, k, N);
while (N > 1) {
exch (pq[1], pq[N]);
fixDownG (pq, 1, --N);
}
}
Quanto tempo heapsort consome? O consumo de tempo é proporcional ao número de comparações entre elementos do vetor. Esse número é no máximo 3 N lg(N): o primeiro loop faz cerca de N/2 iterações com no máximo 2 lg(N) comparações por iteração; o segundo loop faz cerca de N iterações com no máximo 2 lg(N) comparações por iteração. (Na verdade, uma análise mais cuidadosa mostra que o primeiro loop faz N comparações no máximo.)
exch(pq[1],pq[N]); N--;e
exch(pq[1],pq[N--]);são equivalentes?
≥da definição trocados por
≤e vice-versa. Em particular, o primeiro elemento é mínimo. Escreva uma versão especializada da função heapsort que receba um min-heap a[1..N] e rearranje-o de modo que o vetor fique em ordem decrescente. Sua função não deve chamar outras funções (ou seja, o código deve ser auto-suficiente).