Este capítulo examina um importante e sofisticado algoritmo de ordenação de vetores. O algoritmo que discutiremos
rearranja os elementos de um vetor v[1 . . n] de modo que eles fiquem em ordem crescente,
ou seja, de modo que tenhamos v[1] ≤ v[2] ≤ . . . ≤ v[n]. O algoritmo, conhecido como Heapsort, foi descoberto por J.W.J. Williams em 1964. O Heapsort linearítmico, mesmo no pior caso.
Suporemos que os índices do vetor são 1 . . n e não 0 . . n−1 (como é usual em C) pois essa convenção torna o código um pouco mais simples.
Sumário:
Antes de começar a discutir o Heapsort, precisamos aprender a enxergar a árvore binária que está escondida em qualquer vetor. O conjunto de índices de qualquer vetor v[1..m] pode ser encarado como uma árvore binária da seguinte maneira:
Aqui, como no resto deste capítulo, vamos convencionar que as expressões que figuram como índices de um vetor são sempre calculadas em aritmética inteira. Assim, uma expressão da forma f/2 significa ⌊f/2⌋ , ou seja, o piso de f/2.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 |
Para tornar a árvore binária mais evidente, podemos desenhar o vetor em camadas, de tal modo que cada filho fique na camada seguinte à do pai. A figura abaixo é um tal desenho do vetor v[1..56]; os números nas caixas são os índices i e não os valores v[i]. Observe que cada camada, exceto talvez a última, tem duas vezes mais elementos que a camada anterior. Com isso, o número de camadas de um vetor v[1..m] é exatamente 1 + lg(m), sendo lg(m) o piso de log m.
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 | 56 | |||||||||||||||||||||||||
O segredo do algoritmo Heapsort é uma estrutura de dados,
conhecida como heap,
que enxerga o vetor como uma árvore binária.
Há dois sabores da estrutura:
max-heap e min-heap;
trataremos aqui apenas do primeiro,
omitindo o prefixo max
.
Um heap (= monte) é um vetor em que o valor de todo pai é maior ou igual ao valor de cada um de seus dois filhos. Mais exatamente, um vetor v[1..m] é um heap se
v[f/2] ≥ v[f]
para f = 2, . . . , m . (Como já dissemos acima, a expressão f/2 deve ser entendida como ⌊f/2⌋ .)
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
999 | 888 | 777 | 555 | 666 | 777 | 555 | 222 | 333 | 444 | 111 | 333 | 666 | 333 |
Para entender o algoritmo Heapsort,
será preciso tratar, às vezes,
de heaps com defeitos
:
diremos que um vetor v[1..m] é
um heap exceto talvez pelo índice k
se a desigualdade v[f/2] ≥ v[f]
vale para todo f diferente de k.
É fácil rearranjar os elementos um vetor de inteiros v[1..m]
para que ele se torne um heap.
A idea é repetir o seguinte processo
enquanto o valor de um filho for maior que o de seu pai:
troque os valores de pai e filho
e suba
um passo em direção à raiz.
Mais exatamente,
enquanto v[f/2] < v[f],
faça troca (v[f/2], v[f])
e em seguida f = f/2.
A operação de troca
é definida assim:
#define troca (A, B) {int t = A; A = B; B = t;}
Eis o código completo:
// Rearranja um vetor v[1..m] de modo a // transformá-lo em heap. static void constroiHeap (int m, int v[]) { for (int k = 1; k < m; ++k) { // v[1..k] é um heap int f = k+1; while (f > 1 && v[f/2] < v[f]) { // 5 troca (v[f/2], v[f]); // 6 f /= 2; // 7 } } }
(A palavra-chave static está aí apenas para indicar que constroiHeap é uma função auxiliar que não deve ser invocada diretamente pelo usuário final do Heapsort.)
No início de cada iteração controlada pelo for,
o vetor v[1..k] é um heap.
No curso da iteração,
v[k+1]
é incorporado ao heap.
Para isso,
v[k+1] sobe
em direção à raiz
até encontrar sua posição correta no heap.
Em cada iteração do bloco de linhas 6-7, o índice f pula de uma camada do vetor para a camada anterior. Portanto, esse bloco de linhas é repetido no máximo lg(k) vezes para cada k fixo. Segue daí que o número total de comparações entre elementos do vetor (todas acontecem na linha 5 do código) não passa de
m lg(m) .
(Como veremos adiante, é possível ser mais eficiente e transformar v[1..m] em heap com apenas m comparações.)
for (int k = 1; k < m; ++k) { int f = k+1, x = v[k+1]; while (f > 1 && v[f/2] < x) { v[f] = v[f/2]; f /= 2; } v[f] = x; }
O coração de muitos algoritmos que manipulam heaps
é uma função que, ao contrário de constroiHeap,
desce
em direção à base da árvore.
Essa função, que chamaremos peneira,
recebe um vetor qualquer v[1..m] e
faz v[1] descer
até sua posição correta,
pulando de uma camada para a seguinte.
Como isso é feito?
Se v[1] ≥ v[2] e
v[1] ≥ v[3],
não é preciso fazer nada.
Se v[1] < v[2] e
v[2] ≥ v[3],
basta trocar v[1] com v[2] e
depois fazer v[2] descer
para sua posição correta.
Os dois outros casos são semelhantes.
(Veja um rascunho do algoritmo em pseudocódigo.)
No exemplo a seguir,
cada linha
retrata o estado do vetor no início de uma iteração:
85 | 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | 90 | 89 | 97 | 86 |
99 | 85 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | 90 | 89 | 97 | 86 |
99 | 97 | 98 | 85 | 96 | 95 | 94 | 93 | 92 | 91 | 90 | 89 | 97 | 86 |
99 | 97 | 98 | 93 | 96 | 95 | 94 | 85 | 92 | 91 | 90 | 89 | 97 | 86 |
Segue o código da função. Cada iteração começa com um índice p e escolhe o filho f de p que tem maior valor:
static void
peneira (int m, int v[]) {
int f = 2;
while (f <= m) {
if (f < m && v[f] < v[f+1]) ++f;
// f é o filho mais valioso de f/2
if (v[f/2] >= v[f]) break;
troca (v[f/2], v[f]);
f *= 2;
}
}
A função será aplicada a vetores que são heaps exceto talvez por um ou dois índices. A função pode, portanto, ser documentada assim:
// Recebe um vetor v[1..m] que é um heap
// exceto talvez pelos índices 2 e 3 e
// rearranja o vetor de modo a
// transformá-lo em heap.
A seguinte versão é um pouco melhor, porque faz menos movimentações de elementos do vetor (e menos divisões de f por 2):
static void peneira (int m, int v[]) { int p = 1, f = 2, x = v[1]; while (f <= m) { if (f < m && v[f] < v[f+1]) ++f; if (x >= v[f]) break; v[p] = v[f]; p = f, f = 2*p; } v[p] = x; }
Desempenho. A função peneira é muito rápida. Ela faz no máximo lg(m) iterações, uma vez que o vetor tem 1 + lg(m) camadas. Cada iteração envolve duas comparações entre elementos do vetor e portanto o número total de comparações não passa de
2 lg(m) .
O consumo de tempo é proporcional ao número de comparações e portanto proporcional a log m no pior caso.
int p = 1, f = 2; while (f <= m) { if (v[p] < v[f]) { troca (v[p], v[f]); p = f; f = 2*p; } else { if (f < m && v[p] < v[f+1]) { troca (v[p], v[f+1]); p = f+1; f = 2*p; } else break; } }
for (int f = 2; f <= m; f *= 2) { if (f < m && v[f] < v[f+1]) ++f; int p = f/2; if (v[p] >= v[f]) break; troca (v[p], v[f]); }
int x = v[1], f = 2; while (f <= m) { if (f < m && v[f] < v[f+1]) ++f; if (x >= v[f]) break; v[f/2] = v[f]; f *= 2; } v[f/2] = x;
void constroiHeap_2 (int m, int v[]) { for (int p = m/2; p >= 1; --p) peneira_2 (p, m, v); }
(Veja peneira_2 no exercício anterior.) Mostre que constroiHeap_2 faz no máximo (m lg(m))/2 comparações entre elementos do vetor. Refine sua análise para mostrar que, na verdade, a função faz no máximo m comparações.
for (int p = 1; p <= m/2; ++p) peneira_2 (p, m, v);
Não é difícil reunir o que dissemos acima para obter um algoritmo que rearranja um vetor v[1..n] em ordem crescente. O algoritmo tem duas fases: a primeira transforma o vetor em heap e a segunda rearranja o heap em ordem crescente. (Comece fazendo um rascunho do algoritmo.)
// Rearranja os elementos do vetor v[1..n]
// de modo que fiquem em ordem crescente.
void
heapsort (int n, int v[])
{
constroiHeap (n, v);
for (int m = n; m >= 2; --m) {
troca (v[1], v[m]);
peneira (m-1, v);
}
}
No início de cada iteração do for {} valem as seguintes propriedades (invariantes):
A expressão
v[1..m] ≤ v[m+1..n]
é uma abreviatura de
todos os elementos de v[1..m] são
menores ou iguais a
todos os elementos de v[m+1..n]
.
1 | heap | m | crescente | n | |||||||||
888 | 777 | 666 | 555 | 444 | 333 | 222 | 111 | 000 | 999 | 999 | 999 | 999 | 999 |
elementos pequenos | elementos grandes |
Segue daí que v[1..n] estará em ordem crescente quando m for igual a 1. Portanto, o algoritmo está correto.
A animação à direita (copiada de Simon Waldherr / Golang Sorting Visualization) mostra a aplicação do Heapsort a um vetor v[0..79] de números positivos. Cada elemento v[i] do vetor é representado pelo ponto de coordenadas (i,v[i]). (Por algum motivo, a animação não executa as duas últimas iterações.)
Veja outras animações de algoritmos de ordenação:
Quantas comparações entre elementos do vetor a função heapsort executa? A função auxiliar constroiHeap faz n lg(n) comparações no máximo. Em seguida, a função peneira é chamada cerca de n vezes e cada uma dessas chamadas faz 2 lg(n) comparações no máximo. Logo, o número total de comparações não passa de
3 n lg(n) .
Quanto ao consumo de tempo do heapsort, ele é proporcional ao número de comparações entre elementos do vetor, e portanto proporcional a n log n no pior caso. (Entretanto, a constante de proporcionalidade é maior que a do Mergesort e a do Quicksort.)