Gerenciar prioridades com heapq

Em uma fila de prioridades, cada tarefa tem um número de prioridade. Neste tutorial, quanto menor o número, mais cedo a tarefa deve ser atendida.

Quando alguém pede a próxima tarefa, a coleção seleciona o menor valor de prioridade entre as tarefas disponíveis naquele momento. A ordem de chegada só seria decisiva se estivéssemos usando uma fila FIFO comum.

Observe como a tarefa urgente pode ultrapassar uma tarefa que já estava aguardando.

Uma heap mínima pode ser vista como uma árvore binária completa: os níveis são preenchidos da esquerda para a direita. Mas, em Python, ela é armazenada em uma lista comum — não são criados objetos separados para cada nó.

Exemplo de lista: [1, 4, 3, 9, 7, 8]. O valor no índice 0 representa a raiz da árvore.

Leia a lista por níveis: primeiro a raiz, depois seus filhos, depois os nós do nível seguinte.

Em uma heap mínima de números comparáveis, nenhum pai é maior que seus filhos. Essa é a invariante que a estrutura preserva.

Como a raiz é ancestral de todos os elementos, essa regra garante que o menor valor esteja no índice 0. Porém, ela compara cada nó apenas com seus filhos; não exige comparar todos os pares da lista.

Observe que cada ligação pai-filho respeita a regra, embora os valores fora dessas ligações não estejam em ordem crescente na lista.

Os mesmos valores podem formar heaps mínimas diferentes. Por exemplo, [1, 3, 4, 8, 7, 9] também é válida: cada pai continua menor ou igual aos próprios filhos.

Portanto, ao verificar uma heap, não exija uma ordem específica após o índice 0. Verifique as relações entre cada pai e seus filhos.

Importe o módulo heapq e chame heapq.heapify(valores) para transformar uma lista existente em uma heap mínima. A função modifica a lista recebida e retorna None; portanto, não faça valores = heapq.heapify(valores).

Depois da transformação, o menor valor está em valores[0]. Os demais índices representam uma heap válida, mas não uma lista totalmente ordenada.

A raiz da heap contém o menor valor, enquanto os outros valores só precisam respeitar a relação entre pai e filhos.

Execute este trecho e observe o retorno de heapify.

Uma lista vazia ([]) já é uma heap válida. Use heappush(heap, valor) para inserir e heappop(heap) para retirar e obter o menor valor disponível. Ambas preservam a invariante da heap.

Use heap[0] apenas para consultar o menor: essa leitura não remove nada. Tanto heap[0] quanto heappop(heap) levantam IndexError se a heap estiver vazia.

Compare a consulta com a retirada no mesmo estado da heap.

Extrações sucessivas com heappop produzem os valores em ordem crescente. Porém, ao esvaziar a heap, seus elementos são consumidos.

Se precisar manter a heap original, crie uma cópia com copia = heap.copy() e retire da cópia. Não conclua nada pela ordem exibida na lista interna: valide o comportamento pela sequência de valores retirados.

No seu computador, salve como prioridades.py e execute com python prioridades.py. Compare a lista interna com a sequência de extrações.

Uma entrada como (prioridade, tarefa) funciona enquanto as prioridades são diferentes. Mas tuplas são comparadas da esquerda para a direita: se duas prioridades empatam, Python tenta comparar as próprias tarefas para decidir a ordem.

Isso é um problema quando a tarefa é um dicionário, pois dicionários não possuem uma ordenação entre si.

Em um empate, a comparação alcança o objeto armazenado.

Execute este exemplo em um arquivo Python ou no interpretador.

Armazene cada entrada como (prioridade, contador, tarefa). O contador é obtido de um único itertools.count() associado à fila.

Com a mesma prioridade, o menor contador vence. Assim, a heap decide o empate antes de precisar comparar a tarefa. Como o contador cresce a cada entrada, ele preserva a ordem de chegada entre tarefas de mesma prioridade.

A heap compara os campos da tupla nesta sequência.

O desempacotamento ignora os critérios auxiliares quando a tarefa é retirada.

Uma entrada da fila tem a forma (prioridade, contador, tarefa). Se você localizar uma entrada e a substituir por outra com prioridade diferente, todos os itens continuam na lista — mas a relação entre pai e filhos pode deixar de ser válida.

Por isso, não consulte fila[0] nem chame heappop() depois da substituição até restaurar a heap com heapify(fila).

A nova prioridade 0 foi colocada em uma posição cujo pai tem prioridade 2. Isso viola a regra: um pai não pode ser maior que um filho.

heapq não fornece uma operação para encontrar uma tarefa arbitrária e alterar sua prioridade. Para atualizações ocasionais, faça uma varredura da lista, substitua a entrada e execute heapify.

Ao substituir, mantenha o contador original. Assim, se duas tarefas tiverem a mesma prioridade, a que entrou primeiro continua saindo primeiro.

A função recebe uma heap de entradas (prioridade, contador, tarefa) e atualiza uma tarefa identificada por "id".

Para uma lista já preenchida, heapq.heapify(lista) constrói a heap em O(n). Inserir com heappush e retirar o menor com heappop custa O(log n); consultar o menor em heap[0] custa O(1).

Esses custos assumem comparações de custo constante. O crescimento interno da lista também tem custo amortizado, como em outras listas Python.

A estratégia simples de atualização ensinada antes — localizar uma tarefa, substituir a entrada e chamar heapify — custa O(n): a varredura é O(n) e a reconstrução também é O(n). Não é uma atualização O(log n).

Também não use uma heap esperando ordenar uma coleção inteira mais rápido: retirar seus n elementos exige n operações O(log n), totalizando O(n log n).

Uma lista em ordem decrescente permite retirar o menor pelo final com pop(), em O(1). Porém, inserir uma nova tarefa exige encontrar e abrir espaço na posição correta, com custo O(n) para manter a ordenação.

Reordenar a coleção com list.sort() pode custar até O(n log n) a cada ordenação. Na prática, o tempo também depende da ordem atual dos dados, pois a ordenação do Python é adaptável. Portanto, meça cargas equivalentes antes de concluir qual alternativa é mais rápida.

Use uma heap quando novas tarefas chegam enquanto você precisa consultar ou retirar repetidamente a próxima de menor prioridade.

Para um lote estático, sem novas entradas entre a preparação e o consumo, ordenar uma única vez pode ser mais simples e adequado. Se há muitas mudanças arbitrárias de prioridade, a atualização simples por varredura e heapify pode deixar de ser atraente.

Para uma comparação justa, as duas soluções precisam aplicar o mesmo critério: menor prioridade primeiro e, em caso de empate, ordem de entrada.

A estratégia com heapq mantém a heap a cada inserção. A outra mantém uma lista em ordem decrescente após cada inserção; assim, seu menor item fica no final e sai com pop().

Antes de medir, confirme que ambas produzem exatamente a mesma sequência de retiradas.

As duas estruturas recebem as mesmas entradas e entregam as mesmas saídas. A diferença está no trabalho feito entre uma retirada e outra.

Crie um arquivo, por exemplo comparar_heap.py, cole o código abaixo e execute python comparar_heap.py no seu computador.

As cargas são determinísticas. Cada chamada das funções cria sua própria estrutura e seu próprio count(): uma execução medida não reutiliza o estado da anterior.

O script valida a equivalência antes de imprimir o menor tempo por execução em cada cenário.

No cenário de lote, todas as entradas já existem antes da primeira retirada. A lista pode ser ordenada uma única vez, portanto essa alternativa deve entrar na comparação.

Na carga intercalada, cada inserção exige que a lista alternativa seja reordenada novamente. É justamente nesse padrão de manutenção incremental que uma heap costuma ser apropriada.

Não conclua que heapq sempre vence: os tempos dependem do tamanho, da mistura de operações, da máquina e dos custos incluídos no experimento.

Nesta aplicação, cada tarefa é um dicionário, mas a heap armazena tuplas no formato (prioridade, contador, tarefa). O contrato é observável pelas retiradas: menor prioridade numérica sai primeiro e, em caso de empate, a tarefa que entrou antes sai antes.

Após alterar uma prioridade, preserve o contador original e execute heapify. Não teste uma ordem específica da lista interna: uma heap válida só garante que o menor elemento está na posição zero.

Copie o código para um arquivo Python e execute-o. Os asserts verificam a ordem de atendimento, inclusive o empate entre as prioridades 1.

A atualização localiza a entrada, preserva seu contador e reconstrói a heap antes das próximas retiradas.