Esta página analisa o algoritmo Heapsort, inventado por J.W.J. Williams. Ela resolve o seguinte problema de ordenação de vetor:
Problema da ordenação: Rearranjar um vetor A[1 .. n] de modo que ele fique em ordem crescente.
O algoritmo resolve o problema da ordenação usando um max-heap. A rotina Constrói-Max-Heap transforma A[1 .. n] em um max-heap e a rotina Corrige-Descendo transforma o vetor A[1 .. m−1] em max-heap supondo que as subárvores com raizes 2 e 3 são max-heaps.
| Heapsort (A, n) |
| 1 . Constrói-Max-Heap (A, n) |
| 2 . para m := n, n−1, … , 2 |
| 3 .ooo A[1] :=: A[m] |
| 4 .ooo Corrige-Descendo (A, m−1, 1) |
(Note como o algoritmo consegue fazer o serviço
sem usar um vetor auxiliar que sirva como espaço de trabalho
!)
Para entender como a coisa funciona,
observe que no início de cada iteração do bloco de linhas 3-4
temos os seguintes invariantes:
É claro que A[1 .. n] estará em ordem crescente quando m for igual a 1.
| 1 | m | n | ||||||||||
| 888 | 777 | 666 | 555 | 444 | 333 | 222 | 111 | 000 | 999 | 999 | 999 | 999 |
|
elementos pequenos max-heap |
elementos grandes crescente | |||||||||||
No pior caso, Constrói-Max-Heap consome Ο(n) unidades de tempo e cada invocação de Corrige-Descendo consome Ο(lg n) unidades de tempo. Logo, Heapsort consome
Ο(n lg n)
unidades de tempo no pior caso. Assim, o algoritmo é linearítmico.
peçasó, ou seja, não deve invocar outros algoritmos.