2.38. Code di priorità

Una coda di priorità è un contenitore che sa sempre quale dei suoi elementi è il più piccolo (o il più grande) senza ordinare l’intera struttura. heapq ne implementa una in MicroPython usando una semplice list come archiviazione e un algoritmo basato su albero chiamato min-heap per mantenere l’elemento più piccolo all’indice 0.

2.38.1. Il modello mentale

Un min-heap è una lista disposta in modo che l’elemento a ogni indice sia minore-o-uguale agli elementi agli indici 2*i + 1 e 2*i + 2. Questa disposizione rende efficienti tre operazioni:

  • Trovare l’elemento più piccolo – si trova in heap[0]. Un singolo accesso per indice, nessuna scansione.

  • Aggiungere un elemento – risale attraverso l’albero, confrontandosi con un solo genitore per livello. Mille elementi richiedono circa dieci confronti; un milione circa venti.

  • Rimuovere l’elemento più piccolo – lo stesso percorso al contrario, con lo stesso esiguo numero di confronti.

La lista non è ordinata. Iterando su di essa si ottengono gli elementi in ordine arbitrario. Solo heap[0] è garantito essere il minimo.

2.38.2. Le tre funzioni in MicroPython

Il modulo heapq di MicroPython espone esattamente tre funzioni:

  • heapq.heappush() – inserisce un elemento, mantenendo intatto l’invariante dell’heap.

  • heapq.heappop() – rimuove e restituisce l’elemento più piccolo.

  • heapq.heapify() – riorganizza sul posto una lista esistente in un heap.

Questa è l’intera interfaccia. Le funzioni heappushpop, heapreplace, nlargest, nsmallest e merge di CPython non esistono; i pattern seguenti mostrano come costruire manualmente quelle più comuni.

Partendo da 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

Partendo da dati esistenti:

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

Heapify tocca ogni elemento una sola volta ed è notevolmente più veloce che inserire gli stessi elementi uno alla volta.

2.38.3. I primi N su uno stream

Un uso naturale di una coda di priorità: tenere traccia degli N elementi più grandi in uno stream che puoi leggere una sola volta.

Il trucco è mantenere un min-heap di dimensione N. Ogni nuovo valore viene inserito; se l’heap cresce oltre N, si scarta il più piccolo. Il più piccolo è sempre in heap[0], quindi un singolo confronto decide se mantenere o scartare ogni elemento in arrivo:

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)

L’heap non cresce mai oltre N, quindi ogni valore in arrivo costa lo stesso esiguo numero di confronti indipendentemente dalla lunghezza dello stream. La sorted finale è l’unico passaggio il cui costo dipende direttamente da N.

2.38.4. Eventi pianificati

Una coda di priorità di tuple (deadline, payload) è la forma standard per uno scheduler di eventi. Le tuple si confrontano lessicograficamente, quindi la tupla con la deadline più piccola sale automaticamente in cima:

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 due eventi condividono una deadline, il confronto tra tuple passa al secondo elemento. Per payload che non sono naturalmente confrontabili, aggiungi un contatore come secondo elemento della tupla per forzare un ordinamento stabile:

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

Ora il comportamento «deadline più piccola per prima» è intatto, i pareggi si risolvono sul contatore così che le attività pianificate prima vengano eseguite per prime, e task non deve essere confrontabile.

2.38.5. Cosa heapq non offre

Alcuni pattern che sembrano dover funzionare, ma non lo fanno:

  • Iterare con for x in heap non produce un output ordinato – l’ordine sottostante della lista è la disposizione ad albero dell’heap. Per consumare l’heap in ordine, usa heappop finché non è vuoto.

  • Non c’è modo di modificare la priorità di un elemento già presente nell’heap. La soluzione standard è inserire la nuova priorità come voce nuova e contrassegnare la vecchia come annullata (saltandola quando emerge).

  • L’heap memorizza riferimenti ai suoi elementi, non copie. Modificare un elemento dopo che è stato inserito può rompere l’invariante dell’heap. Usa valori immutabili (numeri, tuple) come chiave di confronto.

Un min-heap su una semplice lista è lo strumento giusto per qualunque domanda del tipo «qual è il più piccolo» o «qual è il più urgente» su un piccolo dispositivo embedded. Tre funzioni, una lista, e l’heap si occupa del resto.