Fila de Prioridade em Python com heapq

Para criar uma fila de prioridade em Python, mantenha uma lista, insira itens com heapq.heappush() e remova o menor com heapq.heappop(). Inserção e remoção custam O(log n), enquanto consultar o menor item em heap[0] custa O(1). Como heapq implementa um min-heap, valores numericamente menores saem primeiro.

Uma fila comum preserva a ordem de chegada; uma fila de prioridade entrega primeiro o item mais urgente. Isso serve para escalonadores, busca de caminhos, processamento de chamados, simulações e mesclagem de fluxos. O módulo faz parte da biblioteca padrão. Se a terminologia ainda for nova, o guia de estruturas de dados e algoritmos oferece a base de listas, filas e complexidade.

Como funciona o heap de heapq

Um heap binário mantém uma propriedade: cada pai é menor ou igual aos filhos. A lista não fica totalmente ordenada; apenas o menor elemento é garantido na posição zero. Essa organização parcial explica por que inserir é mais barato do que reordenar toda a lista após cada tarefa.

import heapq
fila = []
heapq.heappush(fila, (2, "gerar relatório"))
heapq.heappush(fila, (1, "restaurar serviço"))
heapq.heappush(fila, (3, "arquivar logs"))
while fila:
prioridade, tarefa = heapq.heappop(fila)
print(prioridade, tarefa)

O resultado começa pela prioridade 1. As tuplas são comparadas campo a campo: primeiro prioridade, depois tarefa. A documentação oficial de heapq também apresenta heapify(), heappushpop(), heapreplace(), nsmallest() e nlargest().

Quando os itens já estão em uma lista, heapq.heapify(itens) transforma-a em heap em O(n), melhor do que inserir os n elementos individualmente em O(n log n). Não use sort() depois: isso até preserva a propriedade, mas paga O(n log n) sem necessidade. Para operações e comportamento de listas, consulte manipulação de listas em Python.

Desempate seguro com um contador

Uma tupla (prioridade, tarefa) falha quando duas prioridades são iguais e os objetos de tarefa não podem ser comparados. Mesmo strings comparáveis criam um desempate alfabético que talvez não represente chegada. A solução robusta é incluir um contador crescente: (prioridade, ordem, tarefa).

import heapq
from dataclasses import dataclass
from itertools import count
@dataclass
class Tarefa:
nome: str
cliente: str
ordem = count()
fila = []
def adicionar(prioridade: int, tarefa: Tarefa) -> None:
heapq.heappush(fila, (prioridade, next(ordem), tarefa))
adicionar(1, Tarefa("corrigir pagamento", "Loja A"))
adicionar(1, Tarefa("liberar pedido", "Loja B"))
adicionar(2, Tarefa("exportar métricas", "Interno"))
while fila:
prioridade, _, tarefa = heapq.heappop(fila)
print(prioridade, tarefa.nome)

O contador garante estabilidade entre prioridades iguais e impede que Python compare instâncias de Tarefa. dataclass deixa o registro legível; o guia de data classes em Python aprofunda valores padrão, ordenação e imutabilidade.

Max-heap e prioridades maiores primeiro

Nas versões em que você precisa trabalhar com a interface tradicional de min-heap, represente prioridade máxima negando o número. A maior prioridade original vira o menor valor interno. Negue somente a chave, não o item inteiro:

import heapq
fila = []
heapq.heappush(fila, (-100, "incidente crítico"))
heapq.heappush(fila, (-20, "dúvida comercial"))
prioridade_negativa, chamado = heapq.heappop(fila)
prioridade = -prioridade_negativa
print(prioridade, chamado)  # 100 incidente crítico

Defina claramente se 1 significa urgente ou baixa prioridade. Muitos bugs surgem não no heap, mas em convenções contraditórias entre produtor e consumidor. Um Enum pode tornar níveis discretos mais claros; veja Enum em Python.

Caso real: reagendar e cancelar tarefas

heapq não possui remoção nem atualização eficiente por identificador. Procurar e alterar um elemento diretamente pode quebrar a propriedade do heap. Uma solução usada em escalonadores é manter um dicionário de entradas ativas, marcar a antiga como removida e inserir uma nova. Elementos obsoletos são descartados ao chegar ao topo, técnica conhecida como remoção preguiçosa.

import heapq
from itertools import count
REMOVIDA = object()
heap = []
ativas = {}
ordem = count()
def adicionar(id_tarefa, prioridade, dados):
if id_tarefa in ativas:
cancelar(id_tarefa)
entrada = [prioridade, next(ordem), id_tarefa, dados]
ativas[id_tarefa] = entrada
heapq.heappush(heap, entrada)
def cancelar(id_tarefa):
entrada = ativas.pop(id_tarefa)
entrada[3] = REMOVIDA
def retirar():
while heap:
prioridade, _, id_tarefa, dados = heapq.heappop(heap)
if dados is not REMOVIDA:
del ativas[id_tarefa]
return id_tarefa, prioridade, dados
raise KeyError("fila vazia")
adicionar("job-7", 5, {"tipo": "email"})
adicionar("job-7", 1, {"tipo": "email urgente"})
print(retirar())

O dicionário oferece acesso médio O(1) à entrada ativa; o heap continua responsável pela seleção O(log n). Entradas removidas consomem memória até alcançarem o topo. Em filas com muitas atualizações e poucas retiradas, considere reconstruir periodicamente o heap com entradas ativas.

heapq, PriorityQueue ou bisect?

heapq é simples, rápido e não sincronizado, ideal para algoritmos e fluxos em uma thread. queue.PriorityQueue encapsula um heap com bloqueios e operações de espera, sendo apropriada para produtores e consumidores em threads. A documentação de queue explica put(), get(), limites e task_done(). Para processos ou sistemas distribuídos, é necessária outra infraestrutura.

bisect.insort() mantém uma lista completamente ordenada: buscar e inserir a posição custa O(log n), mas deslocar elementos custa O(n). Ele é útil quando você percorre frequentemente todos os itens em ordem ou precisa de busca por posição. A documentação oficial de bisect detalha esse compromisso. Se a operação dominante é retirar repetidamente o menor, o heap costuma ser melhor.

Erros comuns

• Usar append: adicionar diretamente não restaura a propriedade; use heappush().
• Achar que a lista está ordenada: somente heap[0] tem posição garantida.
• Remover o índice zero: pop(0) custa O(n) e não reorganiza corretamente; use heappop().
• Ignorar empates: adicione contador antes de objetos não comparáveis.
• Editar prioridade no lugar: reinsira ou execute heapify(); para atualizações frequentes, use remoção preguiçosa.
• Compartilhar entre threads: heapq não oferece bloqueio; proteja o acesso ou use PriorityQueue.

Checklist de implementação

• Documente se números menores ou maiores representam maior urgência.
• Modele entradas como (prioridade, ordem, item).
• Use heapify() para carregar um lote existente.
• Retire com heappop() e trate explicitamente a fila vazia.
• Planeje cancelamento, atualização e limpeza de entradas obsoletas.
• Escolha PriorityQueue quando múltiplas threads precisarem esperar.
• Teste empates, fila vazia, prioridades negativas e grande volume.

Perguntas frequentes

heapq cria min-heap ou max-heap?

A interface tradicional cria um min-heap: o menor elemento fica no topo. Para retirar prioridades numéricas maiores primeiro, negue a chave ou use as APIs máximas disponíveis na versão adotada pelo projeto.

Posso ordenar o heap para visualizar a fila?

Uma cópia pode ser ordenada sem afetar o original. Não dependa da ordem interna além do índice zero. Para consumir em ordem, faça repetidos heappop() sobre uma cópia.

heapq é seguro para threads?

Não oferece sincronização. Use bloqueios próprios quando necessário ou prefira queue.PriorityQueue, que foi projetada para troca segura entre threads.

Quando uma lista ordenada é melhor?

Quando você precisa percorrer todos os elementos em ordem, consultar posições arbitrárias ou tem poucos itens. Para inserir e retirar repetidamente o extremo prioritário, heap costuma escalar melhor.