Heaps e filas de prioridade

Uma árvore que cabe num array

Você poderia usar uma árvore balanceada como fila de prioridade — ela também acha o mínimo em O(log n). Mas isso é caro demais para o que se precisa: a árvore de busca mantém todos os elementos ordenados entre si, e a fila de prioridade só quer saber quem é o primeiro.

O heap enfraquece a regra ao mínimo indispensável: todo pai é menor que seus filhos, e nada é dito sobre a ordem entre irmãos. Essa frouxidão tem uma consequência linda — a árvore pode ser mantida sempre completa, sem buracos. E uma árvore completa não precisa de ponteiros: se ela sempre é preenchida da esquerda para a direita, a posição de cada nó é previsível, e o filho de i está em 2i+1. A árvore inteira vira um array simples.

Sift up, sift down e build-heap

Insira valores e acompanhe o elemento subir até encontrar seu lugar; extraia o mínimo e veja o último elemento assumir a raiz e afundar. Repare que a árvore desenhada e o array embaixo são a mesma coisa — o desenho é só uma leitura dos índices.

A aritmética de índices

# Um heap é uma árvore binária COMPLETA guardada num array.
# "Completa" = todos os níveis cheios, exceto o último, que é
# preenchido da esquerda para a direita, sem buracos.
#
# Essa forma sem buracos é o que permite dispensar ponteiros:
#
#         3            índice:  0  1  2  3   4   5  6
#       /   \          array:  [3, 8, 5, 17, 12, 9, 11]
#      8     5
#     / \   / \        filho esq de i = 2i + 1
#   17  12 9  11       filho dir de i = 2i + 2
#                      pai de i       = (i − 1) // 2

# INVARIANTE do min-heap: pai ≤ ambos os filhos. Só isso.
# Note que é MUITO mais fraca que a da BST:
#   - a raiz é o menor elemento — garantido
#   - a ordem entre irmãos: indefinida
#   - "buscar o valor 12": não há atalho, é O(n)
#
# O heap não é uma estrutura de BUSCA. É uma estrutura de
# PRIORIDADE: ele só sabe responder "qual é o menor?" — e
# responde em O(1). É exatamente essa restrição que o deixa
# mais barato e mais compacto que uma árvore balanceada.

As duas operações

# INSERIR — coloca no fim e sobe (sift up)
def inserir(h, v):
    h.append(v)
    i = len(h) - 1
    while i > 0:
        pai = (i - 1) // 2
        if h[pai] <= h[i]: break       # já está no lugar
        h[pai], h[i] = h[i], h[pai]      # troca com o pai
        i = pai
# Sobe no máximo a altura da árvore: O(log n)

# EXTRAIR O MÍNIMO — tira a raiz, traz o último para cima e afunda
def extrair_min(h):
    menor = h[0]
    ultimo = h.pop()
    if h:
        h[0] = ultimo                    # mantém a árvore completa
        i = 0
        while True:
            e, d, m = 2*i + 1, 2*i + 2, i
            if e < len(h) and h[e] < h[m]: m = e
            if d < len(h) and h[d] < h[m]: m = d
            if m == i: break
            h[i], h[m] = h[m], h[i]      # troca com o MENOR filho
            i = m
    return menor
# Afunda no máximo a altura: O(log n)

# Por que o ÚLTIMO elemento vai para a raiz? Porque é o único
# que pode ser removido do array sem abrir um buraco na árvore.
# A forma completa é sagrada — sem ela os índices param de funcionar.

Na prática: heapq e heapsort

# Em Python: o módulo heapq opera sobre uma list comum.
import heapq

h = []
heapq.heappush(h, 5)          # O(log n)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
heapq.heappop(h)              # → 1  (o menor)  O(log n)
h[0]                          # → espiar o menor  O(1)

heapq.heapify(lista)          # transforma em heap IN-PLACE  O(n)
heapq.nsmallest(10, dados)    # os 10 menores, sem ordenar tudo

# É um MIN-heap. Para max-heap, inverta o sinal:
heapq.heappush(h, -valor)     # e negue de novo ao tirar

# Para prioridade + payload, empurre tuplas (prioridade, ordem, item).
# O segundo campo desempata e evita que o Python tente comparar
# os itens em si (o que estouraria se eles não forem comparáveis).
import itertools
contador = itertools.count()
heapq.heappush(fila, (prioridade, next(contador), tarefa))

# HEAPSORT: build-heap O(n) + n extrações O(log n) = O(n log n)
def heapsort(xs):
    h = list(xs)
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]
# O(n log n) GARANTIDO no pior caso (o quicksort não garante isso)
# e in-place, sem memória extra. Mesmo assim perde para o quicksort
# na prática: os saltos de índice destroem a localidade de cache.

Dijkstra: onde a fila de prioridade brilha

# A aplicação clássica: Dijkstra (menor caminho num grafo).
# A cada passo é preciso pegar o nó não visitado mais próximo —
# exatamente o "extrair mínimo" de uma fila de prioridade.
import heapq

def dijkstra(grafo, origem):
    dist = {origem: 0}
    fila = [(0, origem)]                  # (distância, nó)
    while fila:
        d, u = heapq.heappop(fila)        # O(log n) — o mais próximo
        if d > dist.get(u, float("inf")): continue   # entrada obsoleta
        for v, peso in grafo[u]:
            nova = d + peso
            if nova < dist.get(v, float("inf")):
                dist[v] = nova
                heapq.heappush(fila, (nova, v))   # O(log n)
    return dist

# Sem heap (varrendo a lista para achar o mínimo): O(V²)
# Com heap binário:                                O((V + E) log V)
#
# Para um mapa de ruas com 1 milhão de cruzamentos, isso é a
# diferença entre horas e milissegundos. É o motivo de o GPS
# do seu celular recalcular a rota instantaneamente.

Construindo do zero

Mini projeto: implemente MinHeap com push, pop e peek, sem usar heapq. Depois escreva eh_heap_valido(array) que confere a invariante em todos os nós, e use-a como asserção após cada operação num teste com 10 mil inserções e remoções aleatórias.

Projeto principal: resolva o problema do "top K de um fluxo infinito". Dado um stream de milhões de números (ou de trending topics, ou de latências de requisição), mantenha os K maiores usando O(K) de memória — não é possível guardar tudo. O truque é contraintuitivo: use um min-heap de tamanho K. Cada novo elemento é comparado com a raiz (o menor dos K maiores); se for maior, substitui a raiz e afunda. Custo O(log K) por elemento. Compare com ordenar tudo, que seria O(n log n) e exigiria O(n) de memória.

Desafio extra: implemente um escalonador de eventos — o coração de qualquer simulação de eventos discretos. Um heap de (instante, evento), um laço que extrai sempre o próximo evento no tempo, e eventos que podem agendar novos eventos futuros. Use-o para simular uma fila de banco: chegadas de clientes por processo de Poisson, N caixas, e meça o tempo médio de espera em função de N. Você acabou de escrever a base do que bibliotecas como o SimPy fazem.

Teste sua intuição

Onde você encontra isso