Heap

Lo heap è l'implementazione efficiente della coda con priorità (vedi Code con prioritàEntry chiave-valore; ADT coda con priorità (insert, min, removeMin) con chiave minima = priorità massima; esempio di esecuzione; applicazioni; implementazioni con lista non ordinata e ordinata e relativi costi; ordinamento tramite coda con priorità.Code con priorità →): bilancia i costi, con min() in $\Theta(1)$ e insert, removeMin() in $\Theta(\log n)$.

Albero binario completo

Un albero binario di altezza $h$ è completo se:

• per ogni livello $i$ con $0 \le i \le h - 1$ ci sono $2^i$ nodi (livello pieno);
• al livello $h$ i nodi sono tutti a sinistra delle eventuali mancanze: nessun buco, e al più l'ultimo nodo interno ha solo il figlio sinistro.

Proposizione. Un albero binario completo con $n$ nodi ha altezza $h = \lfloor \log_2 n \rfloor$.

Dimostrazione. I livelli $0, \dots, h-1$ sono pieni e l'ultimo ha almeno un nodo: $2^h = 1 + \sum_{j=0}^{h-1} 2^j \le n \le \sum_{j=0}^{h} 2^j = 2^{h+1} - 1$. Quindi $h \le \log_2 n < h + 1$, cioè $h = \lfloor \log_2 n \rfloor$. $\square$

Definizione di heap

Uno heap è un albero binario completo i cui nodi memorizzano entry e che soddisfa la heap-order property: per ogni nodo $v$ diverso dalla radice, $\text{key}(v) \ge \text{key}(\text{padre}(v))$. Equivale a: ogni nodo ha chiave $\le$ quella dei figli. (Un max-heap inverte la disuguaglianza.) Il nodo last è il più a destra del livello $h$.

Le due proprietà hanno ciascuna un ruolo: la completezza dà altezza $\Theta(\log n)$, l'heap-order mette il minimo in cima (min() in $O(1)$). Chiavi duplicate sono ammesse.

Proprietà (heap con $n$ entry):

1. la radice contiene una entry con chiave minima;
2. le chiavi lungo un cammino dalla radice a una foglia formano una sequenza non decrescente;
3. con chiavi distinte, se $e_i$ è l'entry con $i$-esima chiave più piccola ($e_1$ = radice) e sta a profondità $d$, allora $d < i$ (gli $d$ antenati di $e_i$ sono altrettante entry con chiave minore, più $e_i$ stessa);
4. con chiavi distinte, l'entry con chiave massima sta in una foglia (per assurdo: se fosse in un nodo interno, un suo figlio avrebbe chiave maggiore);
5. per ogni nodo $v$ e ogni nodo $u$ nel sottoalbero $T_v$, $\text{key}(u) \ge \text{key}(v)$ (per transitività lungo il cammino).

Conseguenza della 5: le uniche entry di cui si conosce con certezza il confronto con $P[3]$ sono i suoi antenati (minori) e i suoi discendenti (maggiori). In un heap di 12 entry con chiavi distinte, i discendenti di $P[3]$ sono $P[6]$, $P[7]$ e $P[12]$ (i figli di $P[6]$ sono $P[12]$ e $P[13]$, ma $P[13]$ non esiste): quindi 3 entry hanno certamente chiave maggiore (domanda d'esame ricorrente).

Rappresentazione su array (level numbering)

Un heap sta in un array $P[1..n]$ numerando i nodi per livelli, da sinistra a destra: la radice è $P[1]$, i figli di $P[i]$ sono $P[2i]$ e $P[2i+1]$, il padre di $P[i]$ è $P[\lfloor i/2 \rfloor]$ e $\text{last} = n$. I collegamenti padre-figlio sono impliciti (struttura dati implicita): nessun puntatore, spazio $\Theta(n)$. (Nel testo adottato la numerazione parte da 0: figli $2i+1$, $2i+2$, padre $\lfloor (i-1)/2 \rfloor$.)

Per un albero completo con $n \ge 1$ nodi e altezza $h$: i $2^i$ nodi del livello $i < h$ occupano le posizioni $2^i \le j \le 2^{i+1} - 1$ e quelli del livello $h$ le posizioni $2^h \le j \le n$. Per un albero non completo questo schema può richiedere spazio esponenziale (un cammino di $n$ nodi sempre a destra occupa la posizione $2^n - 1$).

Inserimento: insert(k, x) e up-heap bubbling

Si pone la nuova entry in posizione $\text{last} + 1$ (la completezza è salva) e si ripristina l'heap-order risalendo.

Algoritmo insert(k, x)
e <- (k, x); last <- last + 1; P[last] <- e; i <- last
while i > 1 AND P[floor(i/2)].getKey() > P[i].getKey() do
    swap(P[i], P[floor(i/2)])
    i <- floor(i/2)
return e

Se l'array è pieno si alloca prima un array più grande (ad esempio di taglia doppia): costo ammortizzato.

Invariante del while: l'unica coppia padre-figlio che può violare l'heap-order è $(P[\lfloor i/2 \rfloor], P[i])$. Vale all'inizio (la sola entry nuova può violare) e si conserva: lo scambio porta la chiave minore sopra, e la chiave scesa è $\ge$ l'antenato che ora è sopra di essa. Alla fine $i = 1$ o il padre è $\le P[i]$: nessuna violazione.

Costo: il while fa al più $h$ iterazioni, con $h = \lfloor \log_2 n \rfloor$ ($n$ numero di entry dopo l'inserimento), e c'è un'istanza con esattamente $h$ iterazioni (chiave minore di tutte): $\Theta(\log n)$.

Rimozione del minimo: removeMin() e down-heap bubbling

Si toglie la radice, si porta in radice l'ultima entry e si ripristina scendendo, scambiando sempre con il figlio di chiave minore.

Algoritmo removeMin()
minentry <- P[1]; P[1] <- P[last]; last <- last - 1; i <- 1
while 2*i <= last do
    j <- indice del figlio di P[i] con chiave minima (2i o 2i+1)
    if P[i].getKey() <= P[j].getKey() then break
    swap(P[i], P[j]); i <- j
return minentry

Invariante: $P[j]$ è il figlio di chiave minima di $P[i]$ e le uniche coppie (padre, figlio) che possono violare l'heap-order sono $(P[i], P[2i])$ e $(P[i], P[2i+1])$. Si scambia con il figlio minore perché solo così il nuovo padre di entrambi è $\le$ di tutti e due. Costo: al più $h$ iterazioni, e c'è un'istanza (l'entry di $P[\text{last}]$ ha chiave massima) con $h$: $\Theta(\log n)$.

Rimozione di una entry qualsiasi

removeEntry(P, j): si pone $P[j] \leftarrow P[\text{last}]$ e si decrementa $\text{last}$. Sia $e = (k, v)$ l'entry spostata, $e_0$ il nuovo padre, $e_1, e_2$ i figli. Tre casi:

1. $k_0 \le k \le \min(k_1, k_2)$: l'heap è già valido;
2. $k < k_0$: up-heap bubbling a partire da $P[j]$;
3. $k > \min(k_1, k_2)$: down-heap bubbling a partire da $P[j]$.

Ciascun ciclo fa $O(\log n)$ iterazioni: $\Theta(\log n)$ al caso pessimo (ad esempio $j = 1$ e $P[\text{last}]$ con chiave massima).

Esempio svolto

Heap iniziale $P = [4, 6, 9, 15, 7, 16, 12, 20, 18, 8, 11]$ ($n = 11$, $h = 3$).

• insert(5): $5$ in posizione $12$ (figlio destro di $P[6] = 16$); $5 < 16$ scambio, ora in posizione $6$ con padre $P[3] = 9$; $5 < 9$ scambio, in posizione $3$ con padre $P[1] = 4$; $5 > 4$ stop. $P = [4, 6, 5, 15, 7, 9, 12, 20, 18, 8, 11, 16]$.
• insert(3): $3$ in posizione $13$ (padre $P[6] = 9$) $\to$ sale a $6$ (padre $5$) $\to$ $3$ (padre $4$) $\to$ $1$. $P = [3, 6, 4, 15, 7, 5, 12, 20, 18, 8, 11, 16, 9]$.
• removeMin() restituisce $3$: si mette $9$ in radice, $P = [9, 6, 4, \dots]$; figlio minore $4$ ($9 > 4$) scambio $\to$ posizione $3$, figli $P[6] = 5$ e $P[7] = 12$: minore $5$, scambio $\to$ posizione $6$, figlio $P[12] = 16$: $9 < 16$ stop. $P = [4, 6, 5, 15, 7, 9, 12, 20, 18, 8, 11, 16]$.
• removeMin() restituisce $4$: radice $\leftarrow 16$; figli $6, 5$: scambio con $5$; figli di posizione $3$: $9, 12$: scambio con $9$; $P = [5, 6, 9, 15, 7, 16, 12, 20, 18, 8, 11]$.

(Tutti i passaggi sono stati verificati eseguendo un'implementazione.)

Fatti sulle visite di uno heap

Con $7$ entry a chiavi distinte, la visita in preorder può restituire le entry in ordine crescente (basta che tutte le chiavi del sottoalbero sinistro siano minori di quelle del destro: $1, 2, 3, 4, 5, 6, 7$ per livelli con sinistra $\{2,3,4\}$, destra $\{5,6,7\}$). Inorder e postorder non possono: nell'inorder la radice (chiave minima) è preceduta dai $3$ nodi del sottoalbero sinistro, e nel postorder è l'ultima.

Errori comuni

• Scambiare con il figlio sbagliato nel down-heap (si sceglie il minore, non il sinistro).
• Dimenticare di aggiornare $\text{last}$, o di spostare in radice l'ultima entry (non una qualsiasi) in removeMin.
• Ritenere che uno heap sia ordinato: lo è solo lungo i cammini; non c'è relazione tra fratelli né tra livelli diversi su rami diversi.
• Scambiare le formule dei figli ($2i$, $2i+1$ con indici da 1; $2i+1$, $2i+2$ con indici da 0).