Heapsort

Heapsort
Esta página examina um algoritmo sofisticado que rearranja um vetor dado em ordem crescente. Para que a descrição do algoritmo fique mais simples, convém que os índices do vetor sejam 1..n e não 0..n-1, como é usual em C. Resumindo, nosso algoritmo rearranja os elementos de um vetor v[1..n] de tal modo que ele fique em ordem crescente, ou seja, de tal modo que tenhamos v[1] ≤ v[2] ≤ . . . ≤ v[n]. O algoritmo, conhecido como Heapsort, foi inventado por J.W.J. Williams ["Algorithm 232 (heapsort)",Communications of the ACM, 7, p.347-348, 1964].
Veja o verbete Heapsort na Wikipedia. Veja também o capítulo 14 do "Programming Pearls".
Heap (árvore binária quase completa)
O segredo do funcionamento do algoritmo é uma estrutura de dados conhecida como heap (= monte). Um max-heap é um vetor v[1..m] tal que [estou escrevendo m e não n de propósito]: v[f/2] ≥ v[f] para f = 2, . . . , m. Aqui, como no resto desta página, vamos convencionar que as expressões que figuram como índices de um vetor são sempre inteiras. Uma expressão da forma "f/2" significa ⌊f/2⌋ , ou seja, o piso de f/2, isto é, a parte inteira do quociente de f por 2.
Assim, se v[1..17] é um max-heap então, em particular, v[5] ≥ v[10] e v[5] ≥ v[11]: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 | 999 |
Estranha essa definição de max-heap, não? Talvez a coisa fique mais clara se encararmos a sequência de índices 1..m como um árvore binária: * o índice 1 é a raiz da árvore; * o pai de um índice f é f/2 (é claro que 1 não tem pai); * o filho esquerdo de um índice p é 2p e o filho direito é 2p+1 (é claro que o filho esquerdo só existe se 2p ≤ m e o filho direito só existe se 2p+1 ≤ m).
A figura abaixo procura desenhar um vetor v[1..55] de modo que cada filho fique na "camada" imediatamente inferior à do pai. O vetor é definido por v[i]=i e