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.
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
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
| 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) |
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".