Ordenação: Heapsort

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.

Heapsort

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.

Exercícios

  1. Mostre que, mesmo no melhor caso, o algoritmo Heapsort consome Ω(n) unidades de tempo.
  2. Escreva um algoritmo iterativo que faça o seguinte: recebe um vetor A[1 .. n] que é um max-heap e rearranja o vetor de modo que ele fique crescente. O código de seu algoritmo deve ficar em uma peça só, ou seja, não deve invocar outros algoritmos.
  3. Incorpore os códigos de Constrói-Max-Heap e Corrige-Descendo ao código de Heapsort, ou seja, reescreva Heapsort substituindo as invocações de Constrói-Max-Heap e Corrige-Descendo pelo código correspondente. Faça os ajustes necessários.
  4. Escreva uma variante do Heapsort que rearranje um vetor A[1 .. n] em ordem decrescente.