O que é um heap e como ele implementa uma fila de prioridade?

Question

IT Interview Practice · Accepted Answer

Um **heap binário** é uma árvore binária completa armazenada em um array que mantém a **propriedade de heap**: em um **min-heap**, todo pai é ≤ seus filhos, então o **mínimo sempre está na raiz**. Isso o torna a implementação padrão de uma **fila de prioridade**.

## Layout do array

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## Operações

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — remove root, sift down -> 1
```

## Complexidade

| Operação | Tempo |
|---|---|
| peek min/max | O(1) |
| push (inserir) | O(log n) |
| pop (extrair) | O(log n) |
| construir heap de n itens | O(n) |

## Quando usar

- **Agendamento** por prioridade (ex. agendadores de tarefas do SO).
- **Dijkstra / Prim** algoritmos de caminho mais curto e MST.
- **Top-K** problemas e medianas de streaming.
- **Heap sort** (in-place O(n log n)).

## Por que isso importa

Um heap oferece o próximo item mais importante instantaneamente sem manter tudo completamente ordenado, o que é muito mais barato do que re-ordenar.

É a base de algoritmos orientados por prioridade e uma ferramenta frequente em entrevistas para perguntas sobre "k maiores/menores".

Operação	Tempo
peek min/max	O(1)
push (inserir)	O(log n)
pop (extrair)	O(log n)
construir heap de n itens	O(n)

Layout do array

Operações

Complexidade

Quando usar

Por que isso importa

Perguntas relacionadas