Ordenação por heap

A ordenação por heap (heapsort) é a ordenação por seleção com uma forma melhor de encontrar o maior valor. Guarda os valores por ordenar num heap, uma árvore guardada dentro da própria lista, em que o maior valor está sempre no topo. Retirá-lo e reparar o heap leva cerca de log n passos, em vez de percorrer tudo.

Um heap desenhado como árvore binária por cima dos mesmos valores em barras, com o maior valor na raiz a ser trocado para o fim da lista
Um heap desenhado como árvore binária por cima dos mesmos valores em barras, com o maior valor na raiz a ser trocado para o fim da lista

Uma árvore dentro de uma lista

Um heap binário é uma árvore que não precisa de ponteiros. A posição 0 é a raiz, e os filhos da posição i são as posições 2i + 1 e 2i + 2; assim, as posições 1 e 2 são os filhos da raiz, as posições 3 a 6 o nível seguinte, e assim por diante. Todos os níveis estão cheios, exceto o último, que se preenche a partir da esquerda. Num max-heap cada pai é pelo menos tão grande como os filhos, por isso o maior valor está sempre na raiz.

Afundar

Uma só operação faz todo o trabalho. Para afundar um valor, compare-o com os filhos. Se o filho maior for maior do que o valor, trocam, e o valor é comparado com os novos filhos. Para quando nenhum filho é maior ou quando chega ao fundo. Como a árvore tem só cerca de log₂ n níveis, um afundamento faz no máximo cerca de 2 log₂ n comparações.

Construir o heap e depois ordenar

Para construir o heap, afunde cada pai, do último até à raiz. Cada subárvore já é um heap antes de o seu pai afundar nela. Depois ordene: troque a raiz, o maior valor, com o último valor do heap. Esse valor está agora na posição final. O heap fica uma posição mais curto, e o valor que chegou à raiz afunda para o reparar. Repita até restar um valor.

Um exemplo

Considere 5, 1, 4, 2, 8. Ao construir o heap, 1 afunda para baixo de 8 e depois 5 afunda para baixo de 8, o que dá 8, 5, 4, 2, 1. Agora 8 é trocado para o fim; 1 chega à raiz e afunda, passando por 5 e 2: 5, 2, 4, 1 | 8. Depois 5 vai para o fim e 1 afunda, passando por 4: 4, 2, 1 | 5, 8. Mais duas rondas terminam a lista: 1, 2, 4, 5, 8, após 12 comparações e 10 trocas.

Pontos fortes e fracos

A ordenação por heap leva um tempo proporcional a n log n mesmo no pior caso, e não precisa de memória extra. O quicksort pode abrandar até n² e o merge sort precisa de um buffer tão longo como a lista, por isso a ordenação por heap é a alternativa segura: o introsort, usado pela biblioteca padrão de C++, muda para ela quando as partições do quicksort correm mal. Em computadores reais costuma ser mais lenta do que ambos, porque salta entre posições distantes da lista, e não é estável. J. W. J. Williams publicou a ordenação por heap, juntamente com o heap binário, em 1964.

Experimente

Abra a aplicação e prima Avançar. A árvore por cima das barras mostra o heap: o valor que está a afundar tem uma cor própria, o filho com que é comparado fica realçado, e cada troca aparece tanto na árvore como nas barras. Quando o heap estiver construído, veja a raiz ser trocada para o fim, ficar verde e sair da árvore.

Perguntas frequentes

Qual é a complexidade temporal da ordenação por heap?

O(n log n) no melhor caso, no caso médio e no pior caso. Construir o heap leva O(n), e cada uma das n − 1 extrações leva O(log n). Ordena no lugar com O(1) de memória extra.

Qual é a diferença entre a ordenação por heap e a ordenação por seleção?

Ambas retiram repetidamente o maior (ou o menor) valor restante. A ordenação por seleção encontra-o percorrendo toda a parte por ordenar, n comparações de cada vez. A ordenação por heap guarda a parte por ordenar num heap, onde o maior valor já está no topo, e reparar o heap custa só cerca de log n comparações.

Para que serve um heap além de ordenar?

Para filas de prioridade: um heap dá logo o maior (ou o menor) elemento e permite adicionar ou remover elementos em cerca de log n passos. Escalonadores, o algoritmo de caminhos mais curtos de Dijkstra e simulações de eventos usam todos um heap.

A ordenação por heap é estável?

Não. Trocar a raiz para o fim move valores por longas distâncias, por isso valores iguais podem mudar a sua ordem.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar a ordenação por heap