O módulo heapq sempre foi uma das ferramentas mais úteis da biblioteca padrão para implementar filas de prioridade. Durante muito tempo, sua interface foi orientada principalmente a min-heaps: o menor valor permanece no topo e pode ser removido com eficiência. Nas versões recentes do Python, a API passou a incluir operações explícitas para max-heaps, facilitando casos em que o maior elemento deve ter prioridade. Neste guia, você aprenderá a usar essas funções, entender quando elas fazem sentido e evitar erros comuns em algoritmos reais.
O que é um heap
Um heap é uma estrutura de dados parcialmente ordenada. Em um min-heap, o primeiro item é sempre o menor. Em um max-heap, o primeiro item é sempre o maior. Isso não significa que toda a lista esteja ordenada. O ganho está em inserir e remover o elemento prioritário com custo logarítmico, sem pagar o preço de ordenar toda a coleção após cada alteração.
Esse comportamento é ideal para agendadores, filas de tarefas, seleção dos maiores ou menores valores, algoritmos de grafos, simulações, processamento de eventos e sistemas que precisam atualizar prioridades continuamente.
Por que uma API nativa de max-heap ajuda
Antes das funções específicas para max-heap, era comum inverter números com sinal negativo. Para guardar prioridades 10, 20 e 30, por exemplo, armazenavam-se -10, -20 e -30. A técnica funciona para números, mas deixa o código menos legível e complica tuplas, objetos e comparações customizadas. Uma API explícita evita essa transformação mental e reduz bugs.
import heapq
prioridades = [10, 30, 20, 50, 40]
heapq.heapify_max(prioridades)
print(prioridades[0]) # 50
A função heapify_max reorganiza a lista existente no lugar. O custo é linear, portanto é melhor do que inserir todos os elementos individualmente quando os dados já estão disponíveis.
Inserindo elementos
Depois de criar o heap, use heappush_max para inserir novos valores preservando a propriedade de max-heap.
heapq.heappush_max(prioridades, 60)
print(prioridades[0]) # 60
A inserção não ordena a lista inteira. Ela apenas move o novo item pelos níveis necessários. Por isso, o custo típico é O(log n).
Removendo o maior valor
Use heappop_max para remover e retornar o maior elemento.
maior = heapq.heappop_max(prioridades)
print(maior)
Essa operação também custa O(log n). Em aplicações de fila de prioridade, normalmente o primeiro item representa a tarefa mais urgente, a maior pontuação ou o evento com maior peso.
Substituição eficiente
Quando você precisa remover o maior item e inserir outro imediatamente, heapreplace_max evita duas operações separadas.
removido = heapq.heapreplace_max(prioridades, 25)
A função remove o maior item atual e adiciona o novo valor. É importante notar que o item inserido pode ser maior ou menor do que o removido. Verifique a semântica antes de usar em filtros de tamanho fixo.
Push e pop em uma só etapa
heappushpop_max insere um item e depois remove o maior, de forma otimizada.
removido = heapq.heappushpop_max(prioridades, 35)
Ela é útil quando o heap mantém uma janela de valores e você quer controlar seu tamanho. Ainda assim, a ordem lógica difere de heapreplace_max. Em uma função, o novo valor participa da escolha do maior; na outra, o topo antigo é removido antes da inserção.
Fila de tarefas com prioridade
Em sistemas reais, normalmente armazenamos tuplas. O primeiro campo define a prioridade e os demais servem como desempate e dados da tarefa.
import heapq
from itertools import count
contador = count()
fila = []
def adicionar(prioridade, nome):
heapq.heappush_max(fila, (prioridade, -next(contador), nome))
def proxima():
prioridade, _, nome = heapq.heappop_max(fila)
return prioridade, nome
adicionar(5, "gerar relatório")
adicionar(10, "corrigir indisponibilidade")
adicionar(7, "revisar logs")
print(proxima())
O contador evita comparar diretamente nomes ou objetos quando as prioridades empatam. Em max-heaps, o sinal e a direção do desempate precisam ser escolhidos com cuidado para preservar a ordem desejada.
Objetos personalizados
Você pode usar dataclasses ordenáveis para tornar o código mais expressivo.
from dataclasses import dataclass, field
@dataclass(order=True)
class Tarefa:
prioridade: int
sequencia: int
descricao: str = field(compare=False)
Somente os campos comparáveis participam da ordenação. Se dois objetos não puderem ser comparados, as operações do heap lançarão TypeError. Teste empates explicitamente.
Quando usar min-heap ou max-heap
Use min-heap quando o menor prazo, custo ou distância tiver prioridade. Use max-heap quando a maior pontuação, urgência, receita ou carga precisar sair primeiro. Em alguns algoritmos, um min-heap de tamanho limitado encontra os maiores elementos com eficiência; em outros, um max-heap simplifica a leitura do problema.
Para aprofundar estruturas de dados, consulte o conteúdo sobre estruturas de dados em Python. Também vale revisar listas em Python, tuplas em Python e funções em Python.
Erros comuns
O primeiro erro é tratar o heap como lista ordenada. Apenas o topo tem garantia direta. O segundo é misturar funções de min-heap e max-heap na mesma lista. Isso corrompe a propriedade estrutural. O terceiro é alterar manualmente um item interno sem reconstruir o heap. Se uma prioridade mudar, remova e reinsira o item ou use uma estratégia de invalidação.
Outro problema aparece com valores NaN, comparações inconsistentes ou objetos mutáveis. A relação de ordem deve ser previsível. Em filas concorrentes, proteja o heap com sincronização adequada ou use abstrações prontas.
Desempenho e testes
Teste cenários vazios, um único elemento, prioridades repetidas e grandes volumes. Operações de remoção em heap vazio geram IndexError. Se a entrada vier do usuário, valide antes. Para medir desempenho, use dados representativos e o módulo timeit, evitando conclusões baseadas em coleções minúsculas.
A documentação oficial do módulo heapq é a referência principal. Para entender a análise assintótica, consulte também a visão geral de heaps como estrutura de dados.
Conclusão
As operações nativas de max-heap deixam o código Python mais claro, especialmente quando a regra do domínio realmente privilegia o maior valor. heapify_max, heappush_max, heappop_max, heapreplace_max e heappushpop_max cobrem os principais fluxos de criação, inserção, remoção e substituição. A escolha correta entre essas funções depende da ordem exata das operações e do tamanho que o heap deve manter. Com testes de empate, validação de comparabilidade e uma estratégia clara de atualização de prioridades, o max-heap se torna uma ferramenta eficiente para filas, rankings, agendadores e algoritmos de seleção.
