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)$. È un albero binario (Alberi binariAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.Alberi binari →) tenuto in un array: la struttura implicita sfrutta l'indicizzazione $\Theta(1)$ degli array (Array e stringhe in CArray di dimensione fissa in memoria contigua, inizializzazione, nessun controllo sugli indici, passaggio a funzioni con la lunghezza, matrici; stringhe come array di char terminati da '\0' e funzioni di string.h.Array e stringhe in C →); il codice C è in Alberi e heap in CAlbero binario in C con nodo struct e figli left/right; funzioni ricorsive (conteggio, altezza, visita inorder, liberazione in postorder); inserimento in un albero binario di ricerca con Nodo **; min-heap su array con indici da 1 (insert, removeMin, bottomUp).Alberi e heap in C →. Non va confuso con lo heap della memoria dinamica (Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →): sono due cose diverse con lo stesso nome.

Albero binario completo

Definizione (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.

Esempio. Con $h=2$ i livelli $0$ e $1$ sono pieni ($1+2$ nodi) e il livello $2$ ha da $1$ a $4$ nodi tutti a sinistra: $n$ va da $4$ a $7$.

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

Esempio. $n=8$ dà $h=\lfloor\log_28\rfloor=3$, $n=15$ dà $h=3$ e $n=16$ dà $h=4$.

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$. Qui si usa la somma geometrica finita $\sum_{j=0}^{h-1}2^j = 2^h-1$ (Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →, Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica →), da cui $1 + (2^h - 1) = 2^h$ è il numero minimo di nodi (livelli pieni più un solo nodo nell'ultimo), mentre $2^{h+1}-1$ è il massimo (tutti i livelli pieni). Applicando $\log_2$ a $2^h \le n < 2^{h+1}$ (funzione crescente: Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →) si ottiene $h \le \log_2 n < h + 1$, cioè $h = \lfloor \log_2 n \rfloor$. $\square$

Il grafico mostra l'altezza (e quindi il numero massimo di scambi di insert e removeMin) in funzione di $n$: cresce così lentamente che per $n=1000$ vale $9$ e per un milione $19$.

Definizione di heap

Definizione (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$.

Esempio. L'array $[4,6,9,15,7,16,12]$ è uno heap: $6,9\ge4$, $15,7\ge6$ e $16,12\ge9$.

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). 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).

Esempio. Nello heap $[4,6,9,15,7,16,12]$ la radice $4$ è il minimo e il cammino $4,6,15$ è non decrescente.

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)

Formula (level numbering di uno heap su array). 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$.)

Esempio. In $P[1..11]$ i figli di $P[5]$ sono $P[10]$ e $P[11]$, e il padre di $P[11]$ è $P[\lfloor11/2\rfloor]=P[5]$.

Perché proprio $2i$ e $2i+1$. I livelli precedenti al livello $i$ contengono $1+2+\dots+2^{i-1}=2^i-1$ nodi, quindi il livello $i$ comincia alla posizione $2^i$. Il nodo in posizione $2^i+k$ è il $k$-esimo del suo livello (contando da $0$ a sinistra). I suoi due figli sono il $2k$-esimo e il $(2k+1)$-esimo del livello $i+1$, che comincia alla posizione $2^{i+1}$: le loro posizioni sono $2^{i+1}+2k = 2(2^i+k)$ e $2(2^i+k)+1$, cioè $2j$ e $2j+1$ se $j=2^i+k$ è la posizione del padre. Esempio: $P[5]$ ha figli $P[10]$ e $P[11]$; $P[6]$ ha $P[12]$ e $P[13]$.

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

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

Esempio. Su $P=[4,6,9,15,7,16,12,20,18,8,11]$, insert(5) mette $5$ in posizione $12$ e lo fa salire fino alla $3$: $P=[4,6,5,15,7,9,12,20,18,8,11,16]$.

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 (il ragionamento è quello dell'array estendibile in Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →).

Traccia di insert(5) su $P=[4,6,9,15,7,16,12,20,18,8,11]$:

Due scambi (su un massimo di $\lfloor\log_2 12\rfloor=3$): $P=[4,6,5,15,7,9,12,20,18,8,11,16]$.

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

Proprietà (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.

Esempio. Su $P=[4,6,9,15,7,16,12,20,18,8,11]$, removeMin() restituisce $4$ e lo heap diventa $[6,7,9,15,8,16,12,20,18,11]$.

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)$.

Traccia di removeMin() su $P=[4,6,9,15,7,16,12,20,18,8,11]$ ($\text{last}=11$): restituisce $4$, mette $P[11]=11$ in radice e $\text{last}=10$, ottenendo $[11,6,9,15,7,16,12,20,18,8]$.

Risultato $[6,7,9,15,8,16,12,20,18,11]$, tre scambi, come sopra. Se si scambiasse con il figlio maggiore (ad esempio $9$ al passo 1) il nuovo padre di $6$ sarebbe $9>6$ e l'heap-order verrebbe violato.

Rimozione di una entry qualsiasi

Proprietà (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]$.

Esempio. Su $P=[4,6,9,15,7,16,12,20,18,8,11]$, removeEntry(P, 2) porta $11$ in posizione $2$ e lo fa scendere (down-heap): $P=[4,7,9,15,8,16,12,20,18,11]$.

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).