Heaps e Filas de Prioridade
O que é uma pilha?
Um heap é uma árvore binária completa onde cada pai satisfaz a propriedade heap - seja sempre menor (heap mínimo) ou sempre maior (heap máximo) que seus filhos. "Completo" significa que todos os níveis estão cheios, exceto possivelmente o último, que é preenchido da esquerda para a direita.
1 Min-heap
/ \
3 5
/ \
7 4
Por estar completo, nós o armazenamos em um flat array - sem necessidade de ponteiros. Para índice i: filho esquerdo = 2i + 1, filho direito = 2i + 2, pai = (i - 1) // 2.
Min-Heap vs Max-Heap
| Propriedade | Heap mínimo | Heap máximo | |----------|----------|----------| | Raiz | Elemento menor | Maior elemento | | Pai ≤ Filhos? | ✅ Sim | ❌ Não (≥) | | Extrato dá | Mínimo | Máximo |
O heapq do Python é um min-heap por padrão. Para um heap máximo, negue os valores na inserção e negue novamente na extração.
Inserir e Extrair - Passo a Passo
Inserir - pressione até o final e, em seguida, aumente a bolha (troque com o pai enquanto menor):
import heapq
h = [1, 3, 5, 7]
heapq.heappush(h, 2) # h becomes [1, 2, 5, 7, 3]
Extrair min - troque a raiz com o último elemento, pop por último e peneire (troque com o filho menor):
smallest = heapq.heappop(h) # returns 1
Ambas as operações são executadas em O(log n) porque a altura da árvore é log n.
Heapify - Construindo um Heap em O(n)
Chamar converte uma lista em um heap em O(n), não em O(n log n). Ele funciona de baixo para cima, analisando cada nó que não é folha. Este é um dos resultados de complexidade mais surpreendentes em CS.
Discussão
Entrar participar da discussão