HeapSort
Na seção sobre o algoritmo de ordenação por seleção, vimos que esse algoritmo se resume a encontrarmos o elemento mínimo do vetor de entrada e colocar esse elemento na posição correta. A complexidade de se encontrar o elemento mínimo em um vetor é $O(n)$. Como precisamos encontrar o elemento mínimo $n$ vezes, a complexidade do algoritmo como um todo acaba sendo $O(n^2)$. Mas o que aconteceria se em vez de usar um vetor, usássemos uma estrutura de dados que nos permita encontrar o elemento mínimo a um custo mais baixo? A ideia do Heapsort é exatamente esta.
A cada iteração do Heapsort, selecionamos o elemento mínimo e o colocamos na posição correta. Repetimos esse procedimento para todos os elementos do vetor. Entretanto, em vez de usarmos um arranjo simples, usamos um heap, que nos permite encontrar o elemento mínimo a um custo computacional mais baixo. O custo de se encontrar o menor elemento em um heap é $O(1)$, mas a cada vez que extraímos o menor elemento temos que atualizar o heap – complexidade $O(\log n)$. Como fazemos isso para os $n$ elementos do vetor de entrada, a complexidade assintótica do Heapsort é $O(n \log n)$. A idéia é a mesma do algoritmo de ordenação por seleção, mas por causa da estrutura de dados usada (heap em vez de arranjo simples) a complexidade assintótica acaba sendo bem melhor. O Heapsort é um exemplo de como o uso da estrutura de dados correta pode fazer a diferença entre um algoritmo eficiente e um algoritmo ineficiente.
Agora que já uma ideia de como o Heapsort funciona, vejamos em mais detalhes os aspectos de seu funcionamento.
Funcionamento do Algoritmo
Para o heapsort, assumiremos que as funções promove e demove, vistas na seção sobre heaps foram implementadas para operar em max-heaps ou heaps máximos (elas já foram implementadas assim na seção sobre heaps), heaps em que o maior elemento está no topo. Existem também os min-heaps ou heaps mínimos, nos quais o menor elemento está no topo.
O heapsort opera sobre um arranjo, mas este arranjo deve ser visto de forma especial. O arranjo representa duas estruturas abstratas: um heap na primeira metade do arranjo e na metade direita uma sequencia de elementos em ordem arbitrária (essa mesma sequência vai sendo ordenada à medida em que o algoritmo avança). Essa representação é necessária para que o heapsort seja feito in-place.
O Heapsort é um algoritmo que opera em dois estágios. No primeiro estágio, o arranjo de entrada é transformado em um heap. No segundo estágio, que consiste de $n$ passos, os $n$ elementos do arranjo são extraídos em ordem decrescente e a sequência ordenada é construída no final do arranjo, indo da direita para a esquerda. No primeiro estágio do algoritmo, usamos a função promove, pois precisamos organizar no heap os $n$ elementos do arranjo, um de cada vez. No segundo estágio, repetimos $n$ o seguinte procedimento: removemos o maior elemento do heap, o inserimos no final do arranjo e reorganizamos novamente o arranjo.
Com as ideias acima em mente, o heapsort pode ser implementado da seguinte forma:
def heapsort(A, n):
# Primeiro estágio: construção do heap.
for i in range(2, n):
promove(A, i)
# Segundo estágio: construção da sequência ordenada.
for i in range(n, 1, -1):
A[1], A[i] = A[i], A[1]
demove(A, i - 1)O heapsort é um algoritmo de ordenação in-place, que possui complexidade assintótica $O(n \log n)$ no pior caso, mas que não é estável.
Playground
# Use este espaço para praticar o que você aprendeu nesta seção.
# Basta digitar o código no espaço abaixo e clicar 'run'.