O módulo heapq implementa heaps binários sobre listas Python. Um heap mantém o menor elemento na posição zero e permite inserir ou remover prioridades em tempo logarítmico. Essa estrutura é útil em filas de prioridade, algoritmos de caminho mínimo, agendamento, simulações, processamento de eventos e seleção dos maiores ou menores elementos de um conjunto.
Um heap não é uma lista totalmente ordenada. Apenas a relação entre pais e filhos é garantida. Iterar sobre a lista interna não produz os itens em ordem crescente. Use as operações do módulo e trate a representação como detalhe da estrutura.
Crie um heap vazio
Um heap é uma lista comum.
import heapq
fila = []
heapq.heappush(fila, 5)
heapq.heappush(fila, 2)
heapq.heappush(fila, 8)
print(fila[0])
O menor valor fica em fila[0], mas os demais não estão necessariamente em ordem.
Remova o menor elemento
heappop() remove e retorna o menor item.
while fila:
print(heapq.heappop(fila))
Remover de um heap vazio gera IndexError. Verifique a condição ou trate o caso esperado.
Transforme uma lista com heapify
heapify() reorganiza uma lista existente em tempo linear.
valores = [9, 1, 7, 3, 2]
heapq.heapify(valores)
Isso é mais eficiente que inserir todos os elementos individualmente quando os dados já estão disponíveis.
Filas de prioridade com tuplas
Tuplas são comparadas campo a campo. O padrão mais comum armazena prioridade e valor.
fila = []
heapq.heappush(fila, (10, "relatório"))
heapq.heappush(fila, (1, "alarme"))
prioridade, tarefa = heapq.heappop(fila)
Prioridades menores saem primeiro. Para prioridade maior primeiro, negue números ou use recursos de max-heap disponíveis na versão alvo.
Empates e estabilidade
Se duas prioridades forem iguais, Python tenta comparar o segundo campo. Objetos não comparáveis podem gerar TypeError.
from itertools import count
contador = count()
heapq.heappush(fila, (prioridade, next(contador), tarefa))
O contador também preserva a ordem de inserção entre prioridades iguais.
Não compare tarefas diretamente
Objetos de domínio, dicionários e callbacks não devem participar da comparação.
Use uma tupla (prioridade, ordem, item) ou uma dataclass com campos de comparação controlados.
heappushpop
heappushpop() insere um item e remove o menor em uma operação combinada.
removido = heapq.heappushpop(heap, novo_item)
Ele é eficiente para manter os N maiores elementos vistos até o momento.
heapreplace
heapreplace() remove primeiro o menor e depois insere o novo item.
antigo = heapq.heapreplace(heap, novo_item)
O resultado difere de heappushpop() quando o novo item é menor que o topo. Escolha conforme a regra do algoritmo.
Mantenha os maiores N elementos
Use um min-heap de tamanho fixo.
limite = 100
heap = []
for valor in stream:
if len(heap) < limite:
heapq.heappush(heap, valor)
elif valor > heap[0]:
heapq.heapreplace(heap, valor)
Ao final, o heap contém os maiores valores, mas não está ordenado.
nsmallest e nlargest
nsmallest() e nlargest() selecionam extremos.
top = heapq.nlargest(10, registros, key=lambda x: x.pontuacao)
Para N pequeno em relação ao total, essas funções podem ser melhores que ordenar tudo. Para N próximo do tamanho total, sorted() pode ser mais simples e rápido.
Use key com seleção
As funções de seleção aceitam key, mas heappush() não.
Para um heap persistente, inclua a chave calculada na tupla e evite recalculá-la a cada comparação.
Merge de sequências ordenadas
heapq.merge() combina iteráveis já ordenados sem carregar tudo em memória.
resultado = heapq.merge(arquivo_a, arquivo_b, key=extrair_chave)
for item in resultado:
processar(item)
Cada entrada precisa estar ordenada pela mesma regra. O resultado é lazy.
Atualize prioridades
O módulo não oferece decrease-key direto. Alterar uma tupla dentro da lista pode quebrar o heap.
Uma estratégia segura insere uma nova entrada e marca a antiga como removida. Ao retirar itens, ignore entradas obsoletas.
REMOVIDO = object()
entradas = {}
def adicionar(item, prioridade):
if item in entradas:
remover(item)
entrada = [prioridade, next(contador), item]
entradas[item] = entrada
heapq.heappush(fila, entrada)
def remover(item):
entrada = entradas.pop(item)
entrada[2] = REMOVIDO
Consuma entradas válidas
def retirar():
while fila:
prioridade, ordem, item = heapq.heappop(fila)
if item is not REMOVIDO:
del entradas[item]
return item
raise KeyError("fila vazia")
Entradas removidas ocupam memória até chegarem ao topo. Reconstrua o heap periodicamente se a taxa de atualização for alta.
Max-heaps
Tradicionalmente, Python oferece min-heaps e o padrão para máximos é armazenar prioridades negativas.
heapq.heappush(fila, (-prioridade, ordem, item))
Não negue valores não numéricos. Verifique também as APIs de max-heap disponíveis na versão mínima do projeto.
Complexidade
heappush() e heappop() são O(log n), consultar o topo é O(1) e heapify() é O(n).
Essas garantias não incluem o custo de comparar chaves ou manipular objetos grandes.
Dijkstra e algoritmos de grafos
Filas de prioridade aparecem em Dijkstra, A*, Prim e simulações de eventos.
Em Dijkstra sem decrease-key, insira novas distâncias e ignore entradas antigas quando forem retiradas. Valide pesos não negativos.
Agendamento de eventos
Um heap pode armazenar (instante, ordem, callback).
heapq.heappush(eventos, (quando, next(contador), callback))
Use relógio monotônico para durações e nunca execute callbacks longos dentro de uma seção protegida por lock.
Threads
heapq não sincroniza acesso. Várias threads precisam de lock ou de queue.PriorityQueue.
O artigo de concurrent.futures no Python ajuda a coordenar workers, mas a fila ainda precisa de limites e política de shutdown.
Backpressure
Uma fila de prioridade ilimitada pode crescer até esgotar memória.
Defina capacidade, rejeição, persistência ou descarte por prioridade. Não presuma que consumidores sempre acompanharão produtores.
Objetos mutáveis
Se a prioridade depende de um atributo que muda depois da inserção, a ordem fica incorreta.
Calcule uma chave imutável no momento da entrada e atualize por reinserção quando necessário.
Ordenação final
Para obter todos os itens ordenados, retire repetidamente ou use sorted(heap) se não precisar preservar o heap.
Iterar diretamente sobre a lista interna não é ordenação.
Serialização
A lista interna pode ser serializada, mas isso expõe detalhes da implementação e entradas obsoletas.
Para persistência, salve itens lógicos e prioridades e reconstrua com heapify().
Segurança
Prioridades externas podem monopolizar a fila ou impedir trabalho importante. Aplique autorização, limites e classes de serviço.
Não execute callbacks recebidos de fontes não confiáveis.
Testes
Teste fila vazia, empates, prioridades negativas, atualizações, cancelamento, entradas removidas, top-k, grande volume e concorrência.
Compare resultados com sorted() em testes de propriedade.
Erros comuns
Os erros mais frequentes são assumir que a lista está ordenada, comparar tarefas não comparáveis, alterar prioridades no lugar, confundir heapreplace() com heappushpop(), esquecer estabilidade e permitir crescimento ilimitado.
Conclusão
heapq implementa filas de prioridade eficientes sobre listas. Use tuplas com prioridade e contador, mantenha entradas imutáveis e aplique lazy deletion para atualizações.
Consulte a documentação oficial de heapq, o guia de concurrent.futures no Python e o próximo artigo sobre bisect para listas ordenadas.
