2.38. Filas de prioridade

Uma fila de prioridade é um contentor que sabe sempre qual dos seus itens é o mais pequeno (ou o maior) sem ordenar tudo. O módulo heapq implementa uma em MicroPython usando uma list simples como armazenamento e um algoritmo baseado em árvore chamado min-heap para manter o item mais pequeno no índice 0.

2.38.1. O modelo mental

Um min-heap é uma lista organizada de forma 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 três operações eficientes:

  • Encontrar o item mais pequeno – está em heap[0]. Uma única consulta de índice, sem percorrer a lista.

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

  • Remover o item mais pequeno – a mesma travessia na ordem inversa, com o mesmo conjunto reduzido de comparações.

A lista não está ordenada. Iterá-la devolve os itens por ordem arbitrária. Apenas heap[0] tem garantia de ser o mínimo.

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

O módulo heapq do MicroPython expõe exactamente três funções:

Esta é a interface completa. 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 com dados existentes:

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

A heapificação toca em cada item uma vez e é visivelmente mais rápida 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: registar os N maiores itens num fluxo que só pode ser lido 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 mais pequeno. O mais pequeno está sempre em heap[0], pelo que uma única comparação decide se se mantém ou descarta cada item que chega:

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, por isso cada valor que chega custa o mesmo conjunto de comparações independentemente do comprimento do fluxo. O sorted final é o único passo cujo custo depende directamente de N.

2.38.4. Eventos agendados

Uma fila de prioridade de tuplos (deadline, payload) é a forma padrão para um agendador de eventos. Os tuplos comparam lexicograficamente, pelo que o tuplo 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 partilham um prazo, a comparação do tuplo passa para o segundo elemento. Para payloads que não sejam naturalmente comparáveis, adicione um contador como segundo elemento do tuplo 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 resolvem-se pelo contador para que as tarefas agendadas mais cedo sejam executadas primeiro, e task não precisa de ser comparável.

2.38.5. O que o heapq não oferece

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

  • Iterar for x in heap não devolve resultado ordenado – a ordem subjacente da lista é o layout em árvore do heap. Para consumir o heap por ordem, use heappop até estar vazio.

  • Não há forma de alterar a prioridade de um item já no heap. O contorno padrão é inserir a nova prioridade como uma entrada nova e marcar a antiga como cancelada (ignorá-la quando sair do heap).

  • O heap armazena referências aos seus itens, não cópias. Alterar um item depois de ser inserido pode quebrar o invariante do heap. Use valores imutáveis (números, tuplos) como chave de comparação.

Um min-heap sobre uma lista simples é a ferramenta certa para qualquer questão «qual é o mais pequeno» ou «qual é o mais urgente» num pequeno dispositivo embebido. Três funções, uma lista, e o heap trata do resto.