2.38. Filas de prioridade

Uma fila de prioridade é um contêiner que sempre sabe qual de seus itens é o menor (ou o maior) sem precisar ordenar tudo. O heapq implementa uma no MicroPython usando uma list comum como armazenamento e um algoritmo baseado em árvore chamado min-heap para manter o menor item no índice 0.

2.38.1. O modelo mental

Um min-heap é uma lista organizada de modo que o item em cada índice seja menor ou igual aos itens nos índices 2*i + 1 e 2*i + 2. Essa organização torna baratas três operações:

  • Encontrar o menor item – ele está em heap[0]. Uma única busca por índice, sem varredura.

  • Adicionar um item – ele sobe pela árvore, comparando-se a um pai por nível. Mil itens correspondem a cerca de dez comparações; um milhão, a cerca de vinte.

  • Remover o menor item – o mesmo percurso ao contrário, com o mesmo punhado de comparações.

A lista não está ordenada. Iterar sobre ela retorna os itens em ordem arbitrária. Apenas heap[0] tem garantia de ser o mínimo.

2.38.2. As três funções no MicroPython

O heapq do MicroPython expõe exatamente três funções:

Essa é toda a superfície. As funções heappushpop, heapreplace, nlargest, nsmallest e merge do CPython não existem; os padrões abaixo mostram como construir as mais comuns manualmente.

Começando do zero:

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 3)
>>> heap
[1, 5, 3]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heapq.heappop(heap)
5

Começando a partir de dados existentes:

>>> samples = [5, 1, 3, 2, 4]
>>> heapq.heapify(samples)
>>> samples
[1, 2, 3, 5, 4]
>>> heapq.heappop(samples)
1

Aplicar heapify percorre cada item uma vez e é perceptivelmente mais rápido do que inserir os mesmos itens um a um.

2.38.3. Top-N sobre um fluxo

Um uso natural de uma fila de prioridade: rastrear os N maiores itens em um fluxo que você só pode ler uma vez.

O truque é manter um min-heap de tamanho N. Cada novo valor é inserido; se o heap crescer além de N, descarta-se o menor. O menor está sempre em heap[0], então uma única comparação decide se cada item recebido deve ser mantido ou descartado:

def top_n_brightest(readings, n):
    heap = []
    for r in readings:
        if len(heap) < n:
            heapq.heappush(heap, r)
        elif r > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, r)
    return sorted(heap, reverse=True)

O heap nunca cresce além de N, então cada valor recebido custa o mesmo punhado de comparações, não importa quão longo seja o fluxo. O sorted final é a única etapa cujo custo depende diretamente de N.

2.38.4. Eventos agendados

Uma fila de prioridade de tuplas (deadline, payload) é a forma padrão para um agendador de eventos. Tuplas são comparadas lexicograficamente, então a tupla com o menor prazo flutua automaticamente para o topo:

import heapq
import time

queue = []
heapq.heappush(queue, (time.time() + 5, 'check sensors'))
heapq.heappush(queue, (time.time() + 1, 'blink LED'))
heapq.heappush(queue, (time.time() + 3, 'send heartbeat'))

while queue:
    deadline, task = queue[0]
    now = time.time()
    if now < deadline:
        time.sleep(deadline - now)
    heapq.heappop(queue)
    run(task)

Se dois eventos compartilham um prazo, a comparação de tuplas recorre ao segundo elemento. Para payloads que não são naturalmente comparáveis, adicione um contador como segundo elemento da tupla para forçar uma ordenação estável:

counter = 0
def schedule(deadline, task):
    global counter
    counter += 1
    heapq.heappush(queue, (deadline, counter, task))

Agora o comportamento de menor-prazo-primeiro está intacto, os empates são resolvidos pelo contador de modo que as tarefas agendadas antes sejam executadas primeiro, e task não precisa ser comparável.

2.38.5. O que o heapq não oferece

Alguns padrões que parecem que deveriam funcionar, mas não funcionam:

  • Iterar com for x in heap não produz saída ordenada – a ordem subjacente da lista é o layout em árvore do heap. Para consumir o heap em ordem, use heappop até esvaziá-lo.

  • Não há como alterar a prioridade de um item que já está no heap. A solução padrão é inserir a nova prioridade como uma nova entrada e marcar a antiga como cancelada (ignorando-a quando ela for removida).

  • O heap armazena referências aos seus itens, não cópias. Modificar um item depois de inseri-lo pode quebrar a invariante do heap. Use valores imutáveis (números, tuplas) como chave de comparação.

Um min-heap sobre uma lista comum é a ferramenta certa para qualquer pergunta do tipo “qual é o menor” ou “qual é o mais urgente” em um pequeno dispositivo embarcado. Três funções, uma lista, e o heap cuida do resto.