Heap sort

O algoritmo heapsort
Não é difícil juntar tudo que dissemos acima para obter um algoritmo que coloque v[1..n] em ordem crescente.

// Rearranja os elementos do vetor v[1..n]
// de modo que fiquem em ordem crescente

void heapsort (int n, int v[])
{
int p, m, x; for (p = n/2; p >= 1; --p) peneira (p, n, v); for (m = n; m >= 2; --m) { x = v[1], v[1] = v[m], v[m] = x; peneira (1, m-1, v); }
}

O comando for transforma o vetor em um max-heap recorrendo cerca de n/2 vezes à função peneira. Feito isso, temos um processo iterativo controlado pelo segundo for. No início de cada iteração valem os seguinte invariantes:

o vetor v[1..n] é uma permutação do vetor original, o vetor v[1..m] é um max-heap,

v[1..m] ≤ v[m+1..n] e

o vetor v[m+1..n] está em ordem crescente.
É claro que v[1..n] estará em ordem crescente quando m for igual a 1. 1 max-heap m crescente n
888 777 666 555 444 333 222 111 000 999 999 999 999 999 elementos pequenos elementos grandes

Heapsort: desempenho
Quanto tempo o heapsort leva para fazer o serviço? O tempo é proporcional ao número de comparações entre elementos do vetor, e esse número não passa de

3 n log2n ,

mesmo no pior caso. De fato, o primeiro for constrói o max-heap inicial e faz no máximo n lg(n) comparações entre elementos do vetor. (Uma análise mais cuidadosa revela que o número de comparações não passa de n). O segundo for executa cerca de n chamadas de peneira e cada uma dessas chamadas faz no máximo 2 lg(n) comparações entre elementos do vetor.

Heapsort: animações
Veja applets de animação do algoritmo:

Sorting Algorithms Animation by David R. Martin
Sorting Algorithms na Universidade de British Columbia
Sorting Algorithms, página de Pat Morin na Universidade de Carlton,