Heap sort constrói um heap binário a partir da matriz, depois extrai repetidamente o máximo para produzir ordem classificada. Funciona em O(n log n) e é in-place.
Um max-heap mantém o maior elemento na raiz. Construa o heap (O(n)), depois troque a raiz pelo final, reduza o heap e re-heapify (sift down) — n vezes.
import heapq
def heap_sort(arr):
heapq.heapify(arr) # min-heap in O(n)
return [heapq.heappop(arr) # pop smallest n times
for _ in range(len(arr))]
heap_sort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
Uma implementação clássica o faz no lugar realizando sift down dentro da matriz.
Use quando você precisar de O(n log n) garantido e O(1) memória extra (merge sort precisa de O(n); quicksort corre risco de O(n²)). Não é estável e tem localidade de cache ruim, portanto é frequentemente mais lento na prática do que quicksort. O mesmo heap alimenta filas de prioridade e encontra os k elementos principais.
Heap sort é o único tipo comum que é tanto pior caso O(n log n) quanto in-place, tornando-o valioso em configurações com restrição de memória ou garantia de limite.
A estrutura de heap subjacente é amplamente útil — filas de prioridade, algoritmo de Dijkstra e top-k de streaming.
Cementa a ideia de que a estrutura de dados correta torna um algoritmo eficiente.
Uma biblioteca de perguntas de entrevista de TI com respostas detalhadas — de Júnior a Sênior.
Doar