Como funciona a classificação em heap (heap sort)?

Question

Accepted Answer

**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**.

## A ideia

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.

## Exemplo

```python
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.

## Complexidade

- **Tempo:** O(n log n) em todos os casos. **Espaço:** O(1) in-place.

## Quando usar / armadilhas

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.

## Por que isso importa

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.