Análise do algoritmo Heapsort

[Veja a versão desta página em formato perguntas-e-respostas]

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.

Esta página foi inspirada no capítulo 6 de CLRS. Veja também o verbete Heapsort na Wikipedia.

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 faça

3 ____ A[1] ↔ A[m]

4 ____ 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:

o vetor A[1..m] é um max-heap,
A[1..m] ≤ A[m+1..n] (ou seja, A[1] ≤ A[m+1], A[2] ≤ A[m+2], etc.) e
o vetor A[m+1..n] está em ordem crescente.

É 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 é ene-log-ene.

Exercícios

Mostre que, mesmo no melhor caso, o algoritmo Heapsort consome Ω(n) unidades de tempo.
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 do seu algoritmo deve ficar em uma "peça" só, ou seja, não deve invocar outros algoritmos.
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.
Escreva uma variante do Heapsort que rearranje um vetor A[1..n] em ordem decrescente.