Heap e priority queue: estrarre sempre il migliore

Cos’è una coda di priorità come tipo di dato astratto, come il binary heap la realizza con un semplice array, e perché la stessa struttura compare nella frontiera di A, nel beam di beam search, nel top-k di un LLM e nei k nearest neighbor di una ricerca vettoriale.*

Perché questo capitolo

Una manciata di algoritmi, presi separatamente, sembrano problemi diversi. A* esplora una mappa cercando il cammino più breve. Beam search tiene in vita le k frasi più promettenti durante la generazione di testo. Il decoding top-k di un modello linguistico restringe la scelta ai token più probabili. Una ricerca vettoriale approssimata recupera i documenti più simili a una query. Un agente con dieci task in coda deve decidere quale affrontare per primo. Una simulazione di rete deve sapere quale evento accadrà prima.

Sotto questi sei problemi c’è una sola domanda meccanica: data una collezione che cambia continuamente, qual è l’elemento migliore in questo istante? E migliore può voler dire più vicino, più probabile, più urgente, più imminente. La struttura dati che risponde a questa domanda in modo efficiente si chiama coda di priorità (priority queue), e la sua implementazione canonica è lo heap. Saperla riconoscere significa vedere che A*, beam search e il retrieval di un sistema RAG condividono lo stesso organo interno.

Il capitolo separa con cura due cose che vengono spesso confuse: il contratto — cosa promette una coda di priorità — e l’implementazione — la struttura concreta che mantiene la promessa. La distinzione non è pedanteria accademica. Scegliere l’implementazione giusta cambia di un fattore log n le prestazioni di un planner agentico, e capire perché un binary heap non gestisce bene la decrease-key spiega scelte di design che altrimenti sembrano arbitrarie nel codice di Dijkstra che troverai in produzione.

Contesto

Nel 1964 un ingegnere di nome J.W.J. Williams pubblica su Communications of the ACM un contributo di due pagine: “Algorithm 232: Heapsort” (vol. 7, n. 6, pp. 347-348). L’obiettivo dichiarato è un algoritmo di ordinamento che lavori sul posto, senza memoria aggiuntiva, con garanzia O(n log n) anche nel caso peggiore. Per farlo Williams inventa una struttura dati ausiliaria — lo heap — e si accorge che quella struttura, più che l’ordinamento, è il vero risultato. Lo heap nasce quindi come mezzo per un fine, e diventa subito un fine a sé stesso: la realizzazione standard della coda di priorità.

Pochi mesi dopo, sempre nel 1964, Robert W. Floyd (informatico americano, futuro Turing Award 1978) pubblica “Algorithm 245: Treesort 3” e vi include un miglioramento sottile ma importante: un modo di costruire uno heap da un array disordinato in tempo lineare, invece che inserendo gli elementi uno a uno. Torneremo su questo, perché l’analisi del perché funziona è uno dei piccoli gioielli dell’informatica.

Vent’anni dopo, nel 1984, Michael L. Fredman e Robert E. Tarjan (Turing Award 1986) presentano al simposio FOCS un paper destinato a diventare classico: “Fibonacci heaps and their uses in improved network optimization algorithms” (versione di rivista sul Journal of the ACM, 1987). Il loro Fibonacci heap non è pensato per ordinare: è pensato per rendere più veloce una singola operazione — la decrease-key — perché quella operazione è il collo di bottiglia dell’algoritmo di Dijkstra per i cammini minimi. La struttura discende dai binomial heap, introdotti da Jean Vuillemin nel 1978.

Tre date, tre motivazioni diverse: ordinare (Williams), costruire in fretta (Floyd), accelerare la ricerca su grafi (Fredman-Tarjan). Nella wiki questo capitolo sta a valle di grafi e algoritmi fondamentali, che introduce Dijkstra e Prim senza scendere nei dettagli della coda di priorità che li alimenta, e a valle di A* e euristiche ammissibili, che usa una frontiera senza dire come è fatta dentro. Questo capitolo apre quella scatola.

L’intuizione

Tre angoli per entrare nel concetto, prima di qualunque formalismo.

Angolo 1 — il pronto soccorso

Una coda normale è quella della posta: chi arriva prima viene servito prima. FIFO, first in, first out. Una coda di priorità è quella di un pronto soccorso: non conta da quanto aspetti, conta quanto sei grave. Un paziente con un arresto cardiaco arrivato adesso passa davanti a una distorsione arrivata un’ora fa. A ogni “chiamata del prossimo” il sistema non guarda l’orologio d’arrivo, guarda un punteggio di urgenza — il triage — ed estrae il caso più critico.

Questa è l’intera idea. Una coda di priorità è una collezione dove ogni elemento porta con sé un numero — la priorità — e l’unica operazione di uscita restituisce sempre l’elemento con il numero più basso (o più alto, scelta di convenzione). Non importa quando è entrato. Importa solo il suo posto nell’ordine di gravità. Inserisci pazienti in qualunque momento, e a ogni richiesta esce il più urgente.

Notare cosa la struttura non promette: non ti dice chi è il secondo paziente più grave senza prima togliere il primo, non ti dà la lista ordinata di tutti i pazienti, non risponde a “dov’è il paziente Rossi”. Promette una cosa sola, e la promette bene. Questa parsimonia è ciò che la rende veloce.

Angolo 2 — la piramide in cui ognuno batte i suoi sottoposti

Il secondo angolo riguarda l’implementazione. Immagina una gerarchia aziendale disegnata come piramide. Ogni persona ha un numero — chiamiamolo “anni di anzianità” — e vale una sola regola: ogni capo ha meno anni di anzianità di tutti i suoi sottoposti diretti. Il vertice della piramide è quindi, per forza, la persona meno anziana di tutta l’azienda.

Questa regola è debole. Non dice nulla sul confronto tra due colleghi che non sono uno sopra l’altro: due dirigenti di rami diversi possono avere anzianità in qualsiasi ordine. La gerarchia non è ordinata nel senso pieno; è ordinata solo lungo le linee di comando. Eppure questa regola debole basta per una cosa precisa: guardare il vertice e sapere immediatamente chi è il minimo globale.

E quando il minimo va via? Promuovi temporaneamente al vertice una persona qualsiasi presa dal fondo della piramide, e poi la fai “scendere” scambiandola di posto con il più giovane dei suoi sottoposti finché la regola torna valida. Pochi scambi — tanti quanti i livelli della piramide — e la gerarchia è di nuovo a posto. Questa piramide è lo heap, e quei pochi livelli sono il logaritmo del numero di persone. La regola “ogni capo batte i suoi sottoposti” è la heap property.

Angolo 3 — la stessa famiglia di BFS e DFS

C’è un terzo angolo, ed è il più utile per chi ha già letto ricerca non informata: BFS e DFS. Quel capitolo mostra che BFS e DFS sono la stessa procedura — mantieni una collezione di nodi “da trattare”, estrai uno, processalo, aggiungi i suoi vicini, ripeti — e che l’unica differenza è la politica di estrazione. BFS usa una coda FIFO ed esce sempre il più vecchio. DFS usa una pila LIFO ed esce sempre il più recente.

La coda di priorità è il terzo membro di questa famiglia. La collezione è la stessa, lo scheletro è lo stesso, cambia solo come si sceglie il prossimo: esce sempre quello di priorità minima. Se la priorità è “distanza accumulata dalla sorgente”, ottieni Dijkstra. Se è “distanza accumulata più stima del residuo”, ottieni A*. La coda di priorità non è una curiosità isolata: è il parametro che, sostituito alla coda FIFO, trasforma un attraversamento cieco in una ricerca informata. Tenere a mente questi tre angoli — il triage, la piramide, il membro mancante della famiglia — basta per tutto il resto del capitolo.

La meccanica

ADT contro implementazione

Prima di ogni codice, una distinzione che il capitolo non smetterà di richiamare. Una coda di priorità è un tipo di dato astratto (ADT): una specifica di quali operazioni esistono e cosa fanno, senza dire come. L’interfaccia minima:

insert(x, p) — aggiunge l’elemento x con priorità p.
extract-min() — rimuove e restituisce l’elemento di priorità minima.
peek() — restituisce il minimo senza rimuoverlo.
decrease-key(x, p') — abbassa la priorità di un elemento già presente. Operazione opzionale, e — vedremo — la più insidiosa.

L’ADT è un contratto. L’implementazione è la struttura dati concreta che lo onora. Lo stesso contratto si può onorare in molti modi, con costi diversi:

Implementazione	`insert`	`extract-min`	`peek`
Lista non ordinata	O(1)	O(n)	O(n)
Lista ordinata	O(n)	O(1)	O(1)
Binary heap	O(log n)	O(log n)	O(1)

La lista non ordinata è velocissima a inserire e lentissima a estrarre; la lista ordinata fa l’opposto. Il binary heap non vince su nessuna singola operazione, ma non perde su nessuna: è il compromesso. Quando un carico di lavoro alterna insert ed extract — ed è il caso di quasi tutti gli algoritmi che vedremo — il binary heap domina entrambe le liste. Da qui in poi “heap” significa binary heap, salvo dove diciamo altrimenti.

La proprietà di heap e la forma

Un binary heap rispetta simultaneamente due vincoli.

Il primo è di forma (shape property): è un albero binario completo. Tutti i livelli sono pieni, tranne al più l’ultimo, che si riempie da sinistra a destra senza buchi. Questo vincolo non ha a che fare con i valori: riguarda solo la geometria. La sua conseguenza è che l’altezza dell’albero con $n$ nodi è esattamente $\lfloor \log_2 n \rfloor$ — il più compatto possibile.

Il secondo è la heap property, già incontrata come “ogni capo batte i suoi sottoposti”. In un min-heap: ogni nodo ha chiave minore o uguale a quella di entrambi i suoi figli. Conseguenza diretta: la radice è il minimo globale. In un max-heap vale la disuguaglianza opposta e la radice è il massimo.

È un ordinamento parziale. La heap property vincola solo coppie genitore-figlio, non fratelli né cugini. Questo distingue lo heap da un albero binario di ricerca, dove vale un ordinamento totale (tutto a sinistra minore del nodo, tutto a destra maggiore). Lo heap fa di proposito meno lavoro di ordinamento, e proprio per questo le sue operazioni sono più economiche: non spreca sforzo a ordinare cose che non serve confrontare.

La rappresentazione implicita in array

Qui sta l’idea più elegante della struttura. Poiché l’albero è completo, non serve memorizzarlo con nodi e puntatori: lo si appiattisce in un array, leggendolo livello per livello, da sinistra a destra. La radice in posizione 0, i suoi due figli in posizione 1 e 2, i quattro nipoti da 3 a 6, e così via.

Con indici a base 0, per il nodo all’indice $i$ :

$\text{figlio sinistro} = 2i + 1 \qquad \text{figlio destro} = 2i + 2 \qquad \text{genitore} = \left\lfloor \frac{i - 1}{2} \right\rfloor$

In parole povere: per scendere a un figlio raddoppi l’indice (e aggiungi 1 o 2); per salire al genitore dimezzi. La topologia dell’albero non è memorizzata da nessuna parte — è calcolata dall’aritmetica degli indici ogni volta che serve.

I vantaggi sono concreti. Niente allocazione di nodi, niente puntatori da seguire, zero memoria sprecata in overhead di struttura. E soprattutto: un array è contiguo in memoria, quindi la CPU lo attraversa con ottima località di cache — un fattore costante che, su dati reali, conta più di quanto la notazione O grande lasci vedere. Lo heap è veloce in pratica anche perché è amichevole con la cache.

Sift-up: come funziona l’inserimento

Per inserire un elemento si fanno due mosse. Primo: lo si appende in fondo all’array, cioè come ultima foglia. Questo preserva la forma completa ma può violare la heap property — la nuova foglia potrebbe essere più piccola del suo genitore. Secondo: si ripara con il sift-up (chiamato anche bubble-up, percolate-up, swim).

sift-up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] < heap[parent]:      # min-heap: violazione
            scambia heap[i], heap[parent]
            i = parent                   # risali e ricontrolla
        else:
            break                        # property a posto, fermati

Riga per riga: finché non sei alla radice, guarda il genitore; se sei più piccolo di lui la property è violata, quindi scambiati con lui e risali; appena trovi un genitore più piccolo di te, hai finito. L’elemento “galleggia” verso l’alto finché trova il suo livello. Poiché ogni iterazione sale di un livello e i livelli sono $\lfloor \log_2 n \rfloor$ , il costo nel caso peggiore è O(log n).

Sift-down: come funziona l’estrazione

extract-min restituisce la radice — il minimo — ma toglierla lascia un buco in cima. La procedura: si prende l’ultima foglia dell’array e la si mette al posto della radice (così la forma resta completa e l’array si accorcia di uno). Quella foglia promossa quasi certamente viola la heap property verso il basso. Si ripara con il sift-down (bubble-down, percolate-down, sink).

sift-down(heap, i, n):
    while True:
        left, right = 2*i + 1, 2*i + 2
        smallest = i
        if left  < n and heap[left]  < heap[smallest]: smallest = left
        if right < n and heap[right] < heap[smallest]: smallest = right
        if smallest == i:
            break                        # nessun figlio più piccolo
        scambia heap[i], heap[smallest]
        i = smallest                     # scendi e ricontrolla

Riga per riga: individua i due figli; trova il più piccolo fra il nodo e i suoi figli; se il nodo è già il più piccolo, la property vale e ci si ferma; altrimenti scambia con il figlio minore e scendi in quella direzione. Attenzione al dettaglio: si scambia sempre con il minore dei due figli, altrimenti dopo lo scambio la property fra il nuovo genitore e l’altro figlio sarebbe violata. Anche questo costa O(log n): si scende al massimo per l’altezza dell’albero.

peek() invece è O(1): il minimo è sempre heap[0], basta leggerlo.

Build-heap: costruire in tempo lineare

Dato un array disordinato di $n$ elementi, come trasformarlo in uno heap? La via ovvia: parti da uno heap vuoto e fai $n$ insert, ciascuna O(log n), per un totale O(n log n). Funziona, ma c’è di meglio.

Il metodo bottom-up di Floyd: applica sift-down a tutti i nodi interni, partendo dall’ultimo (indice $\lfloor n/2 \rfloor - 1$ ) e risalendo fino alla radice. Le foglie si saltano: una foglia, da sola, è già uno heap valido di un elemento.

build-heap(array):
    n = len(array)
    for i from n//2 - 1 down to 0:
        sift-down(array, i, n)

La sorpresa è il costo: O(n), non O(n log n). L’intuizione: sift-down su un nodo non costa sempre $\log n$ , costa quanto l’altezza di quel nodo — e nello heap quasi tutti i nodi sono in basso, dove l’altezza è minuscola. Metà dei nodi sono foglie (altezza 0, sift-down gratis). Un quarto sono a altezza 1 (un solo scambio possibile). Un ottavo a altezza 2. Solo la radice ha altezza piena $\log n$ .

Sommando, a altezza $h$ ci sono al più $n/2^{h+1}$ nodi, ognuno costa $O(h)$ :

$\sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot h \;=\; \frac{n}{2} \sum_{h=0}^{\log n} \frac{h}{2^h}$

In parole povere: questa somma dice che il lavoro totale è $n/2$ moltiplicato per una serie. E la serie $\sum_h h/2^h$ converge a un numero finito — esattamente 2 — invece di crescere con $n$ . Quindi l’intera costruzione costa $O(n)$ . Il lavoro pesante riguarda pochissimi nodi vicino alla cima; la massa dei nodi, in basso, costa quasi nulla. Inserire uno a uno paga il logaritmo pieno per ogni elemento; costruire dal basso lo paga solo per i pochi che stanno in alto.

Heapsort: la struttura torna al suo scopo originale

Williams inventò lo heap per ordinare, e l’algoritmo è immediato una volta che hai le operazioni. Per ordinare in modo crescente: costruisci un max-heap dell’array in O(n); poi, $n$ volte, scambia la radice (il massimo) con l’ultimo elemento dello heap, riduci di uno la dimensione logica dello heap, e fai sift-down della nuova radice. Ogni massimo estratto si deposita nella sua posizione finale, dal fondo verso l’inizio. Dopo $n$ estrazioni l’array è ordinato.

Costo: O(n) per la costruzione più $n$ estrazioni da O(log n) ciascuna, totale O(n log n), garantito anche nel caso peggiore. Heapsort lavora in loco, con O(1) memoria aggiuntiva, e non è stabile (non preserva l’ordine relativo di elementi con chiave uguale). Rispetto a quicksort — che è O(n log n) in media ma O(n²) nel peggiore — heapsort non ha casi patologici; rispetto a mergesort — anch’esso O(n log n) garantito — heapsort non chiede memoria extra. Per questo introsort, l’algoritmo di ordinamento di molte librerie standard, parte con quicksort e ripiega su heapsort quando rileva che quicksort sta degenerando: heapsort è la rete di sicurezza.

Costo delle operazioni per implementazione: tavola di sintesi

Questa tabella confronta le principali implementazioni della priority queue, includendo la decrease-key che è il vero discriminante per gli algoritmi su grafi:

Implementazione	`insert`	`extract-min`	`decrease-key`	`build`
Lista non ordinata	O(1)	O(n)	O(1)	O(n)
Lista ordinata	O(n)	O(1)	O(n)	O(n log n)
Binary heap	O(log n)	O(log n)	O(n) / O(log n)†	O(n)
d-ary heap	O(log_d n)	O(d log_d n)	O(log_d n)†	O(n)
Fibonacci heap	O(1) ammort.	O(log n) ammort.	O(1) ammort.	O(n)
Pairing heap	O(1) ammort.	O(log n) ammort.	O(log n) ammort.	O(n)

† Con un heap indicizzato (mappa elemento → indice); senza, la ricerca dell’elemento è O(n).

Il caso d’uso principale che differenzia le strutture è Dijkstra su grafi sparsi: con un binary heap il costo è $O((V+E)\log V)$ , con un Fibonacci heap scende a $O(E + V \log V)$ — un miglioramento reale solo quando $E \ll V^2$ , cioè su grafi molto sparsi. Su grafi densi ( $E = \Theta(V^2)$ ) le due complessità coincidono.

Il problema della decrease-key

decrease-key(x, p') abbassa la priorità di un elemento già nello heap. Serve eccome: in Dijkstra, quando si scopre un cammino più corto verso un nodo già in frontiera, la sua priorità va abbassata. La correzione algoritmica è facile: abbassare una chiave può violare la property solo verso l’alto, quindi basta un sift-up, O(log n).

Il problema vero è a monte. Per fare sift-up di un elemento devi sapere dove si trova nell’array. E un binary heap nudo non lo sa: la heap property non aiuta a localizzare un valore arbitrario, perché non c’è ordine tra rami diversi. Cercarlo significa scorrere tutto l’array — O(n). La decrease-key ingenua costa quindi O(n), e questo distrugge la complessità di Dijkstra.

Ci sono tre risposte, tutte importanti perché le incontrerai nel codice reale.

Binary heap indicizzato. Si affianca allo heap una mappa hash elemento → indice corrente nell'array. Ogni scambio dentro sift-up e sift-down aggiorna la mappa. Così decrease-key diventa: lookup O(1) per trovare l’indice, più sift-up O(log n). Totale O(log n). È la soluzione pulita usata nelle implementazioni serie di Dijkstra e Prim. Costa la disciplina di mantenere la mappa sincronizzata a ogni scambio.

Lazy deletion. Invece di modificare la priorità di un elemento presente, si inserisce una nuova copia con la priorità aggiornata, lasciando la vecchia nello heap. Quando una copia obsoleta emerge da extract-min, la si riconosce e la si scarta. Lo heap può gonfiarsi — fino a $O(E)$ entry su un grafo con $E$ archi — ma ogni operazione resta O(log E), e poiché $E \le V^2$ si ha $\log E = O(\log V)$ : la complessità asintotica non peggiora. È la tecnica del modulo heapq di Python e di moltissime implementazioni di A*. Spesso è preferita perché evita di tenere sincronizzata una mappa di indici: più semplice da scrivere bene.

Strutture più avanzate. Il d-ary heap generalizza il binary heap dando a ogni nodo $d$ figli invece di 2. L’albero diventa più basso ( $\log_d n$ livelli), quindi sift-up e decrease-key accelerano; in cambio sift-down deve confrontare $d$ figli per livello. Conviene quando le insert e le decrease-key dominano sulle estrazioni — come in Dijkstra su grafi densi. Il Fibonacci heap spinge oltre, ed è il prossimo paragrafo.

Fibonacci heap: il ruolo teorico

Fredman e Tarjan progettarono il Fibonacci heap nel 1984 con un bersaglio preciso: la decrease-key. La loro struttura ottiene insert e decrease-key in tempo ammortizzato O(1), ed extract-min in O(log n) ammortizzato. “Ammortizzato” significa: non ogni singola operazione è così veloce, ma la media su una lunga sequenza lo è — alcune extract-min fanno lavoro di riordino arretrato per conto delle molte decrease-key quasi gratuite.

L’effetto su Dijkstra è netto. Con un binary heap, Dijkstra costa $O((V + E) \log V)$ , perché ogni arco può scatenare una decrease-key da O(log V). Con un Fibonacci heap le decrease-key diventano O(1) ammortizzato e il costo scende a $O(E + V \log V)$ — ottimale, in senso teorico, per un Dijkstra basato su confronti. Lo stesso guadagno vale per l’algoritmo di Prim sul minimum spanning tree.

E qui serve un’avvertenza onesta, perché è un classico fraintendimento. Il Fibonacci heap, in pratica, si usa raramente. Le costanti nascoste dietro la O grande sono alte; la struttura è fatta di liste di alberi collegate da puntatori, con località di cache pessima; l’implementazione corretta è laboriosa. Su grafi reali, un binary heap o un d-ary heap indicizzato batte il Fibonacci heap malgrado la sua complessità asintotica peggiore. Il Fibonacci heap è soprattutto un risultato teorico: dimostra quale limite è raggiungibile in linea di principio. Strutture successive — il pairing heap in particolare — inseguono lo stesso vantaggio asintotico con costanti praticabili, e il pairing heap è spesso il vincitore concreto quando serve davvero una decrease-key rapida. La lezione è generale: la classe di complessità dice cosa è possibile, non cosa conviene.

Esempi

Esempio 1 — numerico: costruire uno heap a mano

Min-heap vuoto, array []. Inseriamo nell’ordine 5, 3, 8, 1.

insert 5: array [5]. Niente da riparare.
insert 3: appendi in fondo, [5, 3]. L’elemento 3 è all’indice 1, genitore all’indice 0 e 5. Poiché $3 < 5$ , scambia: [3, 5].
insert 8: appendi, [3, 5, 8]. L’8 è all’indice 2, genitore all’indice 0 e 3. Poiché $8 > 3$ , nessuno scambio: [3, 5, 8].
insert 1: appendi, [3, 5, 8, 1]. L’1 è all’indice 3, genitore a $\lfloor (3-1)/2 \rfloor = 1$ , cioè 5. Poiché $1 < 5$ , scambia: [3, 1, 8, 5]. Ora l’1 è all’indice 1, genitore all’indice 0 e 3. Poiché $1 < 3$ , scambia: [1, 3, 8, 5].

Lo heap finale è [1, 3, 8, 5]: la radice 1 è il minimo. Ora extract-min: restituisce 1, sposta l’ultima foglia 5 in cima, [5, 3, 8]. Sift-down: i figli di 5 sono 3 e 8, il minore è 3, e $5 > 3$ , quindi scambia: [3, 5, 8]. Property ristabilita, nuovo minimo 3. Notare che l’array [1, 3, 8, 5] non è mai stato ordinato: solo le relazioni genitore-figlio lo erano.

Esempio 2 — codice: uno scheduler di task per un agente

Un agente con più task pendenti deve affrontare prima i più urgenti. In Python, il modulo heapq fornisce un binary heap min su una lista comune.

import heapq
import itertools

class TaskQueue:
    def __init__(self):
        self._pq = []
        self._counter = itertools.count()   # tie-break stabile

    def add(self, task, priority):
        # convenzione: priorità più bassa = più urgente
        entry = (priority, next(self._counter), task)
        heapq.heappush(self._pq, entry)

    def next(self):
        if not self._pq:
            return None
        priority, _, task = heapq.heappop(self._pq)
        return task

Il dettaglio non ovvio è il counter. Le entry sono tuple, e Python confronta le tuple elemento per elemento: se due task hanno la stessa priority, Python proverebbe a confrontare i task stessi — che magari non sono confrontabili e sollevano un errore. Il contatore intero, sempre crescente e sempre unico, va in mezzo: rompe ogni pareggio prima che il confronto arrivi al task, e per di più fa vincere chi è stato inserito prima (un comportamento FIFO a parità di priorità). È lo stesso pattern raccomandato dalla documentazione ufficiale di heapq.

Esempio 3 — scenario reale: la frontiera di A*

In A* e euristiche ammissibili la frontiera (open set) è l’insieme dei nodi scoperti ma non ancora espansi. A* a ogni passo espande il nodo con $f(n) = g(n) + h(n)$ minimo, dove $g$ è il costo già accumulato e $h$ la stima euristica del costo residuo. Quella frontiera è una coda di priorità, con $f(n)$ come chiave.

frontiera = priority_queue()
frontiera.insert(start, f(start))
while frontiera non vuota:
    nodo = frontiera.extract-min()        # il più promettente
    if nodo == goal: return ricostruisci_cammino()
    for vicino in vicini(nodo):
        nuovo_g = g(nodo) + costo(nodo, vicino)
        if nuovo_g < g(vicino):           # trovato cammino migliore
            g(vicino) = nuovo_g
            frontiera.insert(vicino, nuovo_g + h(vicino))

L’ultimo insert è dove la decrease-key farebbe la sua comparsa: il vicino potrebbe essere già in frontiera con un $f$ più alto. La maggior parte delle implementazioni reali non fa una vera decrease-key; re-inserisce il vicino con il nuovo $f$ e, al momento del pop, scarta le copie obsolete — la lazy deletion vista sopra. La coda di priorità è l’organo che trasforma lo slogan “esplora sempre la cosa più promettente” in un algoritmo eseguibile.

Esempio 4 — top-k: trovare i k migliori senza ordinare tutto

Hai uno stream di un milione di punteggi e ti servono solo i 10 più alti. Ordinare tutto costa $O(n \log n)$ e produce 999.990 risultati che butti via. Meglio: mantieni un min-heap di dimensione $k$ (qui $k = 10$ ).

import heapq

def top_k(stream, k):
    heap = []
    for x in stream:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:                 # x batte il peggiore dei top-k
            heapq.heapreplace(heap, x)    # pop del minimo + push di x
    return sorted(heap, reverse=True)

L’invariante: lo heap contiene sempre i migliori $k$ visti finora, e la sua radice heap[0] è il peggiore di quei $k$ — la soglia da battere. Per ogni elemento, un confronto O(1) con la radice, e al più un heapreplace da O(log k). Totale O(n log k), memoria O(k). Quando $k \ll n$ , la differenza con O(n log n) è enorme. È esattamente la logica della funzione heapq.nlargest della libreria standard di Python — e, come vedremo, la logica del top-k in mezza dozzina di posti diversi di un sistema AI.

Esempio 5 — build-heap passo-passo su un array piccolo

Questo esempio traccia l’algoritmo di Floyd su un array di 6 elementi per rendere concreto il costo O(n). Partiamo dall’array disordinato [9, 4, 7, 2, 6, 1] (indici 0-5) e lo trasformiamo in un min-heap in loco.

Il primo nodo interno (cioè il primo che ha almeno un figlio) è all’indice $\lfloor 6/2 \rfloor - 1 = 2$ . Applichiamo sift-down a partire da lì, risalendo verso la radice.

Array iniziale: [9, 4, 7, 2, 6, 1]
Indici:          0  1  2  3  4  5

Passo 1 — sift-down sul nodo 2 (valore 7). I figli di 2 sono 5 (valore 1). L’indice 6 sarebbe fuori array, quindi il nodo 2 ha un solo figlio. Il figlio 1 < 7, quindi scambia: [9, 4, 1, 2, 6, 7]. Il nodo è sceso all’indice 5 (foglia), fine.

Passo 2 — sift-down sul nodo 1 (valore 4). I figli di 1 sono gli indici 3 (valore 2) e 4 (valore 6). Il minore è 2 all’indice 3. Poiché $4 > 2$ , scambia: [9, 2, 1, 4, 6, 7]. Il nodo è sceso all’indice 3 (foglia), fine.

Passo 3 — sift-down sul nodo 0 (valore 9), la radice. I figli sono gli indici 1 (valore 2) e 2 (valore 1). Il minore è 1 all’indice 2. Poiché $9 > 1$ , scambia: [1, 2, 9, 4, 6, 7]. Ora il nodo è all’indice 2; i suoi figli sono l’indice 5 (valore 7). Poiché $9 > 7$ , scambia: [1, 2, 7, 4, 6, 9]. Il nodo è all’indice 5 (foglia), fine.

Array finale (min-heap): [1, 2, 7, 4, 6, 9]

Verifica: ogni genitore è minore dei suoi figli. Il nodo 0 (valore 1) batte i nodi 1 e 2 (valori 2 e 7). Il nodo 1 (valore 2) batte i nodi 3 e 4 (valori 4 e 6). Il nodo 2 (valore 7) batte il nodo 5 (valore 9). L’intero processo ha richiesto 4 scambi su 6 elementi: il nodo 0 era il più costoso, ma le foglie (nodi 3, 4, 5) non sono state toccate. Questo conferma l’intuizione alla base del costo O(n).

Esempio 6 — merge di k liste ordinate con heapq

Unire $k$ liste già ordinate in un’unica lista ordinata è un problema classico. La soluzione naiva ordina tutto assieme — O(N log N) dove $N$ è il totale degli elementi — ma non sfrutta il fatto che le liste siano già ordinate. La soluzione con un heap è O(N log k): si paga solo il logaritmo del numero di liste, non degli elementi.

import heapq

def merge_k_sorted(lists):
    """
    Unisce k liste ordinate in ordine crescente.
    Ogni elemento dello heap è (valore, indice_lista, indice_elemento).
    """
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    result = []
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        next_idx = elem_idx + 1
        if next_idx < len(lists[list_idx]):
            heapq.heappush(heap, (lists[list_idx][next_idx], list_idx, next_idx))

    return result

# Esempio
lsts = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
print(merge_k_sorted(lsts))   # [1, 2, 3, 4, 5, 6, 7, 8, 9]

Lo heap contiene al massimo $k$ elementi simultaneamente — uno per ogni lista, il “frontiere” corrente. A ogni heappop si estrae il minimo globale, si avanza nel puntatore della lista da cui proveniva, e si reinserisce il successivo. Il costo totale è $O(N \log k)$ , con memoria O(k) per lo heap.

Questo pattern emerge in molti contesti di un sistema AI: il merge di shard di un indice vettoriale distribuito, la fusione di candidate list provenienti da più retriever in un sistema RAG con multiple fonti, l’aggregazione di eventi da più stream ordinati per timestamp in una simulazione multi-agente. La funzione heapq.merge della libreria standard di Python implementa esattamente questo algoritmo.

Applicazioni pratiche

La coda di priorità è una di quelle strutture che, una volta che impari a vederla, compare ovunque in un sistema AI. Tutti gli usi che seguono sono varianti delle quattro operazioni di base.

La frontiera della ricerca informata. A*, Dijkstra e best-first search mantengono il loro open set come coda di priorità. In grafi e algoritmi fondamentali si vede che il costo di Dijkstra dipende direttamente dall’implementazione dello heap: con un binary heap indicizzato è $O((V+E)\log V)$ . Per un planner agentico che cerca su uno spazio di stati, la coda di priorità è il cuore del loop.

Il beam di beam search. In beam search e suoi limiti la generazione mantiene a ogni passo le $k$ sequenze parziali più promettenti per punteggio cumulato. Selezionare quel beam dai molti candidati generati è un top-k: un heap di dimensione $k$ lo fa in $O(n \log k)$ per passo, l’esempio 4 quasi alla lettera.

Il top-k nel decoding di un LLM. Quando un modello linguistico genera un token, la strategia di campionamento top-k restringe la scelta ai $k$ logit più alti prima di applicare il softmax. Su un vocabolario di decine di migliaia di token, è una selezione parziale — i $k$ migliori — non un ordinamento completo. Stessa struttura, altro travestimento.

Il top-k retrieval nei sistemi RAG. Un sistema RAG, dato un punteggio di similarità tra la query e ogni documento, recupera i $k$ documenti più simili da passare al modello. Concettualmente è un nlargest sui punteggi di similarità: i $k$ migliori, non l’intera classifica.

I k nearest neighbor nella ricerca vettoriale. Questo è il ponte verso ann-intro (in preparazione), il prossimo capitolo della Parte. Una ricerca approssimata su grandi insiemi di vettori — i metodi che ann-intro (in preparazione) introdurrà — esplora solo una parte dello spazio e mantiene lungo il cammino un heap dei $k$ vicini migliori trovati finora. Un max-heap di dimensione $k$ permette due cose in O(1): leggere qual è il candidato peggiore attualmente nei top-k, e quindi decidere se un nuovo punto va inserito; e — confrontando quel peggiore con i limiti dell’area ancora da esplorare — decidere quando potare, cioè smettere di cercare in una direzione che non può più migliorare il risultato. La coda di priorità non è un dettaglio della ricerca vettoriale: è la struttura che la rende interrompibile.

Lo scheduling di task agentici. Un agente che gestisce più task pendenti — chiamate a tool, sotto-obiettivi, richieste in attesa — li ordina per urgenza o importanza con una coda di priorità, come nell’esempio 2.

La simulazione a eventi discreti. In una simulazione event-driven (una rete, un sistema di code, un sistema multi-agente) il motore tiene una coda di priorità degli eventi futuri, ordinata sul tempo di occorrenza. extract-min restituisce sempre il prossimo evento da elaborare, che a sua volta può schedulare nuovi eventi. La coda di priorità è il battito di ogni simulatore a eventi.

Il merge di shard e il top-k distribuito. Come mostrato nell’esempio 6, fondere $k$ risultati parziali ordinati in un unico risultato globale è una delle operazioni più comuni in sistemi distribuiti di ricerca e retrieval. Un motore di ricerca che partiziona l’indice su $k$ server raccoglie le top- $m$ liste locali di ciascuno e le fonde con un heap: O(M log k) dove $M = k \cdot m$ è il totale degli elementi ricevuti. Un sistema RAG con più retriever paralleli — uno basato su ricerca lessicale BM25, uno su embedding densi, uno su un grafo di conoscenza — aggrega i candidati di ciascuno nello stesso modo, poi applica un reranker. La coda di priorità è la colla silenziosa che tiene insieme questi strati.

La selezione in Monte Carlo Tree Search. In Monte Carlo Tree Search la fase di selezione scende nell’albero preferendo nodi con valore UCB (Upper Confidence Bound) alto. Quando il numero di figli da considerare è grande, mantenere un max-heap dei candidati permette di recuperare sempre il migliore in O(1) senza scorrere tutta la lista. Non è il cuore strutturale di MCTS — l’albero rimane la struttura principale — ma una coda di priorità nella selezione accelera le implementazioni su alberi con branching factor elevato.

Dove si rompe

La coda di priorità è una struttura solida, ma le aspettative sbagliate intorno a essa generano bug e scelte di design infelici. Questa sezione raccoglie i punti dove le cose si rompono, perché valgono quanto i meccanismi.

Lo heap non è una struttura ordinata. È il fraintendimento numero uno. La sequenza dell’array di uno heap non è ordinata; solo le relazioni genitore-figlio sono vincolate. L’array [1, 3, 8, 5] dell’esempio 1 è uno heap valido e non è ordinato. Lo heap produce una sequenza ordinata se estrai tutti gli elementi uno a uno — ed è esattamente heapsort — ma in sé rappresenta solo un ordinamento parziale. Aspettarsi che iterare sull’array dia gli elementi in ordine è un errore che il codice non segnala: restituisce semplicemente risultati sbagliati.

Heap vs albero binario di ricerca: due contratti diversi, non due implementazioni dello stesso. Un albero binario di ricerca (BST) bilancia l’ordinamento totale: la chiave di ogni nodo è maggiore di tutte le chiavi nel suo sottoalbero sinistro e minore di tutte quelle nel destro. Una traversata in-order restituisce gli elementi ordinati; cercare un valore arbitrario costa O(log n). Lo heap, al contrario, impone un ordinamento parziale: solo lungo le catene genitore-figlio. Non c’è ordine garantito tra fratelli o cugini. La conseguenza pratica: lo heap trova il minimo in O(1) e lo estrae in O(log n), ma per trovare un valore arbitrario deve scorrere l’array — O(n). Il BST fa il contrario: la ricerca è O(log n) su qualsiasi chiave, ma estrarre il minimo è comunque O(log n) (scendi sempre a sinistra). Quando serve solo l’estremo — sempre il minimo, sempre il massimo — lo heap vince per semplicità e costanti basse. Quando servono ricerche arbitrarie, range query o iterazione ordinata, il BST (o meglio, un balanced BST come un albero rosso-nero) è la scelta giusta. Confondere i due porta a strutture con la complessità sbagliata per il problema che si sta risolvendo.

Trovare un elemento arbitrario è O(n). Lo heap risponde a una sola domanda — qual è il minimo — e basta. “Contiene il valore $x$ ?”, “qual è il secondo più piccolo?”, “dov’è l’elemento $y$ ?” non hanno risposte veloci: richiedono di scorrere l’array. Se il tuo carico di lavoro fa molte di queste interrogazioni, lo heap è la struttura sbagliata; ti serve un albero di ricerca bilanciato o una struttura indicizzata. È un caso di scelta di ADT sbagliata, non di heap mal implementato.

La decrease-key è una trappola silenziosa. Come visto, la decrease-key ingenua su un binary heap è O(n) per via della ricerca. Un’implementazione di Dijkstra scritta in fretta che fa decrease-key cercando linearmente il nodo funziona — restituisce il cammino giusto — ma gira in $O(V \cdot E)$ invece di $O((V+E)\log V)$ . Il bug non è di correttezza, è di prestazioni, e si manifesta solo su grafi grandi. La cura è scegliere consapevolmente tra heap indicizzato e lazy deletion fin dall’inizio.

build-heap non costa O(n log n). L’errore opposto, ma altrettanto comune: credere che costruire uno heap costi sempre O(n log n). Il bottom-up di Floyd è O(n); solo l’inserimento ripetuto è O(n log n). Chi non conosce il metodo bottom-up a volte riscrive a mano un build-heap inefficiente, o sceglie una struttura diversa convinto che lo heap “costi troppo a costruirlo”. Se hai già tutti gli $n$ elementi, costruisci dal basso.

Il Fibonacci heap non è “il migliore”. La tabella delle complessità asintotiche mette il Fibonacci heap davanti a tutti, e questo induce a sceglierlo. In pratica è quasi sempre l’opzione sbagliata: costanti alte, puntatori sparsi, località di cache pessima. Su dati reali un binary heap lo batte regolarmente. La complessità asintotica è una guida su cosa è possibile, non un ordine di preferenza pratico — confondere le due cose è un classico errore da manuale letto male. La struttura più usata nei rari casi in cui la decrease-key O(1) ammortizzata serve davvero è il pairing heap (Fredman, Sedgewick, Sleator, Tarjan — 1986), che ottiene bound simili con un’implementazione molto più semplice: una lista collegata di alberi, senza la contabilità di grado dei Fibonacci heap. Il pairing heap è la scelta di molte librerie di ottimizzazione su grafi che richiedono una decrease-key rapida senza voler pagare la complessità del Fibonacci heap.

Min-heap e max-heap: convenzione, non sostanza, ma va dichiarata. Un max-heap si ottiene da un min-heap negando le chiavi. Il modulo heapq di Python è solo min-heap; per un max-heap si inseriscono priorità negate (fino a Python 3.14, che aggiunge varianti _max esplicite). Il bug tipico: dimenticare un segno meno, e ottenere un sistema che dà sistematicamente la priorità opposta — l’agente affronta prima i task meno urgenti, il retrieval restituisce i documenti meno simili. Anche qui nessun crash: solo risultati invertiti.

Lo heap, la memoria e l’omonimia. Lo “heap” struttura dati non ha alcun rapporto con lo “heap” della gestione della memoria — la regione da cui malloc o new allocano. Sono omonimi storici, concetti del tutto scorrelati. La confusione è innocua finché resta lessicale, ma può disorientare chi legge un sistema senza sapere quale dei due “heap” il codice intende.

Le chiavi che cambiano da sole. Lo heap assume che le priorità degli elementi non cambino mentre sono nello heap, se non tramite decrease-key. Se il tuo codice mantiene riferimenti agli oggetti dentro lo heap e ne muta i campi che determinano la priorità, la heap property si corrompe in silenzio e extract-min smette di restituire il vero minimo. Una priorità, una volta che l’elemento è nello heap, è di proprietà dello heap.

Cache-unfriendliness del binary heap su heap grandi. La rappresentazione in array è amichevole con la cache quando l’heap è piccolo — tutto entra in cache L1 o L2. Ma su heap di decine di milioni di elementi, i salti di sift-down — dall’indice $i$ all’indice $2i+1$ o $2i+2$ — diventano salti a indirizzi lontani in memoria, generando frequenti cache miss. Il problema si aggrava perché sift-down scende fino alle foglie, e le foglie costituiscono metà dell’array ma sono sparse su un range di indirizzi grande. Il d-ary heap — dove ogni nodo ha $d$ figli — mitiga il problema: l’albero è più basso ( $\log_d n$ livelli), quindi sift-down ha meno livelli da percorrere e tocca meno locazioni lontane. Con $d = 4$ o $d = 8$ la cache hit rate migliorata compensa il costo dei $d$ confronti per livello. In benchmarking su grafi con centinaia di migliaia di nodi, il 4-heap batte spesso il binary heap pur avendo la stessa classe di complessità asintotica.

Coda di priorità vs coda ordinata: il falso trade-off. Un errore che si vede in codice di intervista e in prototype di agenti: sostituire la priority queue con una lista ordinata, perché “così si vede tutto in ordine”. La lista ordinata ha extract-min in O(1) e peek in O(1), ma insert in O(n) — devi trovare il punto giusto e spostare elementi. Per carichi che alternano frequentemente insert ed extract (il caso tipico di una frontiera di ricerca o di uno scheduler di task) la lista ordinata è O(n) per operazione, contro O(log n) dello heap. La differenza è un fattore $n/\log n$ : su diecimila task è circa 750× più lento. La lista ordinata è utile solo se si fanno quasi esclusivamente extract e pochissimi insert — altrimenti è la struttura sbagliata.

Chiavi di priorità composita e il problema dell’unicità. Quando la priorità non è un semplice numero ma una chiave composta — un f-score con tie-break sull’ID del nodo, una coppia (urgenza, timestamp), una metrica multi-criterio — nascono due trappole. La prima è l’ordine di confronto: Python confronta le tuple elemento per elemento, quindi (3, nodo_A) è confrontato prima su 3, poi sull’identità di nodo_A. Se gli elementi non hanno un ordine naturale, il confronto solleva un’eccezione a runtime. Il pattern corretto è inserire un contatore intero come secondo elemento, garantendo che i confronti non arrivino mai agli oggetti — ed è esattamente il motivo del self._counter nell’esempio 2. La seconda trappola è la semantica: con una chiave composta, due elementi con la stessa priorità primaria ma ID diversi sono diversi per lo heap, anche se per la tua logica sarebbero equivalenti. Una decrease-key fatta maldestramente su una chiave composta può creare duplicati che non vengono mai riconosciuti come obsoleti dalla lazy deletion — se la vecchia entry e la nuova hanno forme di chiave diverse, il marker REMOVED non funziona. Pianificare la struttura della chiave prima di scrivere il primo heappush evita ore di debug.

Collegamenti

A* e euristiche ammissibili — la frontiera di A* è una coda di priorità ordinata su $f = g + h$ ; questo capitolo apre la struttura che A* usa come scatola chiusa.
Grafi e algoritmi fondamentali — Dijkstra e Prim si appoggiano a una coda di priorità; il loro costo dipende da quale heap la implementa.
Ricerca non informata: BFS e DFS — BFS usa una coda FIFO, DFS una pila LIFO, la coda di priorità è il terzo membro della stessa famiglia “collezione più politica di estrazione”.
Beam search e suoi limiti — il beam è un top-k mantenuto a ogni passo con un heap di dimensione $k$ .
Monte Carlo Tree Search — la fase di selezione ordina nodi candidati per valore, un compito da coda di priorità.
ann-intro (in preparazione) — la ricerca approssimata dei vicini mantiene un heap dei $k$ nearest neighbor correnti e lo usa per decidere quando potare.
Big-O come lingua franca — l’analisi di build-heap O(n) è un esempio istruttivo di somma che converge invece di crescere.
greedy-beam (in preparazione) — il decoding top-k di un LLM seleziona i $k$ logit più alti del vocabolario, un top-k su decine di migliaia di candidati.

Per andare oltre

J.W.J. Williams, “Algorithm 232: Heapsort”, Communications of the ACM, vol. 7, n. 6 (1964), pp. 347-348. Il contributo originale di due pagine che introduce sia lo heap sia heapsort.
Michael L. Fredman, Robert E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms”, Journal of the ACM, vol. 34, n. 3 (1987). Il paper che introduce il Fibonacci heap e dimostra il bound $O(E + V \log V)$ per Dijkstra.
Thomas H. Cormen et al., Introduction to Algorithms (CLRS), capitolo 6 (“Heapsort”) e capitolo 19 (“Fibonacci Heaps”). Trattazione di riferimento di heap, heapsort, build-heap O(n) e analisi ammortizzata dei Fibonacci heap.
Documentazione ufficiale del modulo heapq di Python — https://docs.python.org/3/library/heapq.html. Implementazione pratica, le funzioni nlargest/nsmallest e il pattern raccomandato per la coda di priorità con decrease-key via lazy deletion.
Voci “Binary heap” e “Heapsort” di Wikipedia in inglese — https://en.wikipedia.org/wiki/Binary_heap. Buon riferimento per le formule degli indici, la tabella di complessità e il confronto fra il build-heap di Floyd e quello di Williams.
Real Python, “The Python heapq Module: Using Heaps and Priority Queues” — https://realpython.com/python-heapq-module/. Tutorial pratico con i pattern di heappushpop, heapreplace, nlargest/nsmallest e la priority queue con lazy deletion; ottimo punto di partenza per il codice applicativo.
Michael L. Fredman, “On the efficiency of pairing heaps and related data structures”, Journal of the ACM, vol. 46, n. 4 (1999). Il pairing heap è la struttura che in pratica si avvicina di più ai bound del Fibonacci heap con costanti accettabili; questo paper è il punto di partenza per chi vuole esplorare le strutture di heap avanzate oltre il binary heap.
Daniel D. Sleator e Robert E. Tarjan, “Self-Adjusting Heaps”, SIAM Journal on Computing, vol. 15, n. 1 (1986). Introduce i leftist heap e gli skew heap, due varianti che supportano il merge efficiente di due heap — un’operazione che il binary heap non supporta — con diverse garanzie di ammortizzazione.