Costruzione di uno heap

Problema. Input: array $P[1..n]$ di entry. Output: lo stesso array riorganizzato in modo da rappresentare uno heap (vedi HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap →). Entrambe le soluzioni lavorano in loco (senza array aggiuntivi). L'up-heap e il down-heap bubbling sono quelli di HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap →; per i conti sulle somme servono SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie → e la serie geometrica (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 →), e per le dimostrazioni per induzione Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →.

Top-down: $n-1$ inserimenti successivi

Definizione (costruzione top-down con inserimenti successivi). Si considera $P[1]$ uno heap di un elemento e si inserisce $P[2], P[3], \dots, P[n]$ con l'up-heap bubbling.

Esempio. Con $P=[3,2,1]$: $P[1]=3$ è uno heap; insert di $2$ lo fa salire sopra $3$ ($[2,3]$); insert di $1$ sale fino alla radice ($[1,3,2]$).

for j <- 2 to n do
    up-heap bubbling a partire da P[j]

Invariante (alla fine dell'iterazione $j$): $P[1..j]$ rappresenta uno heap, $P[j+1..n]$ è immutato.

Formula (costo della costruzione top-down). Costo. L'iterazione $j$ costa $O(\log j)$, quindi $O\big(\sum_{j=2}^{n} \log j\big) = O(n \log n)$. È anche $\Omega(n \log n)$: se $P$ è in ordine decrescente ogni nuova chiave è minore di tutte le precedenti e sale fino alla radice, e

$$\sum_{j=\lfloor n/2 \rfloor}^{n} \log_2 j \ \ge\ \frac n2 \log_2 \Big\lfloor \frac n2 \Big\rfloor \in \Omega(n \log n).$$

Quindi $\Theta(n \log n)$ (anche $n$ insert consecutive in uno heap vuoto, vedi Esercizio 13 · costruzione di uno heap top-down e bottom-up).

Perché la disuguaglianza della somma. I termini $\log_2 j$ con $\lfloor n/2 \rfloor \le j \le n$ sono almeno $n/2$ (per $n$ pari sono $n/2+1$) e ciascuno vale almeno $\log_2\lfloor n/2\rfloor$, perché il logaritmo è 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 →). Inoltre $\log_2\lfloor n/2\rfloor \approx \log_2 n - 1$, che per $n$ grande è $\Theta(\log n)$: il prodotto è $\Omega(n\log n)$. Con l'array decrescente ogni iterazione $j$ fa tanti scambi quanti il livello del nodo $j$, cioè $\lfloor\log_2 j\rfloor$.

Esempio. $P = [2, 10, 27, 9, 11, 13, 5]$: dopo $j = 2,3$: $[2, 10, 27]$; $j = 4$ ($9$ sale sopra $10$): $[2, 9, 27, 10]$; $j = 5$: $[2, 9, 27, 10, 11]$; $j = 6$ ($13$ sopra $27$): $[2, 9, 13, 10, 11, 27]$; $j = 7$ ($5$ sopra $13$, poi $5 > 2$ stop): $[2, 9, 5, 10, 11, 27, 13]$. Gli scambi sono stati $0,0,1,0,1,1$, in tutto $3$.

Bottom-up: dalle foglie verso la radice

Definizione (costruzione bottom-up). Le posizioni $\lfloor n/2 \rfloor + 1, \dots, n$ sono foglie e quindi già heap da un elemento. Si procede a ritroso sui nodi interni, "sistemando" ciascuno con il down-heap bubbling: ogni nodo ha come sottoalberi due heap già costruiti.

Esempio. Con $n=6$ si ha $\lfloor n/2\rfloor=3$: $P[4..6]$ sono foglie e si sistemano $j=3,2,1$ con il down-heap bubbling.

for j <- floor(n/2) downto 1 do
    down-heap bubbling a partire da P[j]

Invariante (alla fine dell'iterazione $j$): $P[j..n]$ rappresenta una foresta di heap, $P[1..j-1]$ è immutato. Alla fine $j = 1$ e $P[1..n]$ è uno heap.

Formula (costo della costruzione bottom-up). Costo. Sia $h = \lfloor \log_2 n \rfloor$. Il down-heap da un nodo al livello $i$ ($0 \le i \le h-1$) costa $O(h - i)$ (al più la distanza dalle foglie), e al livello $i$ ci sono al più $2^i$ nodi. Il costo totale è

$$O\Big( \sum_{i=0}^{h-1} 2^i (h - i) \Big) = O\Big( 2^h \sum_{i=0}^{h-1} \frac{h - i}{2^{h-i}} \Big) = O\Big( 2^h \sum_{\ell=1}^{h} \frac{\ell}{2^\ell} \Big).$$

Si dimostra per induzione che $\sum_{\ell=1}^{h} \frac{\ell}{2^\ell} = 2 - \frac{h+2}{2^h} < 2$: per $h = 1$ è $\frac12 = 2 - \frac32$; passando da $h$ a $h+1$ si somma $\frac{h+1}{2^{h+1}}$ e si ottiene $2 - \frac{2(h+2) - (h+1)}{2^{h+1}} = 2 - \frac{h+3}{2^{h+1}}$. (Nel corso si dimostra la limitazione più debole $\sum \ell (1/2)^\ell < 3$, che basta.) Dunque il costo è $O(2^h) = O(n)$, perché $2^h \le n$.

Come si arriva alla somma $\sum \ell/2^\ell$. Un nodo al livello $i$ ha sotto di sé al massimo $h-i$ livelli, quindi il suo down-heap fa al più $h-i$ scambi. Con la sostituzione $\ell=h-i$ (distanza dalle foglie) si ha $2^i=2^{h-\ell}=2^h/2^\ell$, da cui $\sum_i 2^i(h-i)=2^h\sum_{\ell}\ell/2^\ell$. Il punto chiave è che il peso $\ell$ cresce linearmente mentre il numero di nodi con quella distanza si dimezza a ogni passo verso l'alto: la serie converge (vedi Criteri del rapporto e della radice per le seriePer una serie a termini positivi, se il limite di a_(n+1)/a_n (criterio del rapporto) o di radice n-esima di a_n (criterio della radice) è L < 1 la serie converge, se è L > 1 diverge; con L = 1 il criterio non dice nulla.Criteri del rapporto e della radice per le serie →: il rapporto tra termini consecutivi tende a $\frac12<1$) e la somma resta limitata da una costante. Controllo con $h=3$: $\frac12+\frac24+\frac38=\frac{11}{8}=2-\frac{5}{8}$, coerente con la formula $2-\frac{h+2}{2^h}=2-\frac58$. Ed è $\Omega(n)$: servono almeno $\lfloor n/2 \rfloor$ iterazioni. $\Theta(n)$.

Perché il bottom-up è più veloce. Nel top-down le iterazioni costose sono molte: i $2^i$ nodi del livello $i$ costano $\Theta(i)$ ciascuno (più sono numerosi, più costano). Nel bottom-up i livelli più numerosi (vicini alle foglie) costano poco, $\Theta(h - i)$, e solo i pochi nodi in alto costano $\Theta(\log n)$.

Numero massimo di scambi del bottom-up, per $n=15$ (albero perfetto, $h=3$): $8$ foglie a distanza $0$ dal fondo, $4$ nodi con al più $1$ scambio, $2$ con al più $2$, $1$ con al più $3$: $4\cdot1+2\cdot2+1\cdot3=11$, contro i $34$ del top-down sull'array decrescente. Per questo il costo è lineare e non $n\log n$.

Esempio. $P = [2, 10, 27, 9, 11, 13, 5, 30, 18, 1, 14, 15, 6]$ ($n = 13$, $\lfloor n/2 \rfloor = 6$):

Un altro esempio (da un tema d'esame): $P = [11, 9, 7, 13, 3, 4]$ con $\lfloor 6/2 \rfloor = 3$: $j = 3$: $P[3]=7$ ha come unico figlio $P[6]=4<7$, scambio, $[11, 9, 4, 13, 3, 7]$; $j = 2$: $P[2]=9$ ha figli $P[4]=13$ e $P[5]=3$, il minore è $3<9$, scambio, $[11, 3, 4, 13, 9, 7]$; $j = 1$: $P[1]=11$ ha figli $3$ e $4$, minore $3$, scambio (ora $11$ è in posizione $2$ con figli $13$ e $9$), minore $9<11$, scambio, $[3, 9, 4, 13, 11, 7]$ ($11$ scende scambiando con $3$, poi con $9$). Totale $4$ scambi.

Altre costruzioni

Fusione di due heap come alberi (non necessariamente completi, altezze $h_1, h_2$) in tempo $O(h_1 + h_2)$: si rimuove una foglia $v$ da $T_1$, si crea una nuova radice con la entry di $v$ e come figli $T_1$ e $T_2$, poi si esegue il down-heap dalla radice.

Definizione (heap sort). Costruzione bottom-up $\Theta(n)$ e poi $n$ removeMin da $\Theta(\log n)$: $\Theta(n \log n)$ (vedi Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →).

Esempio. Con $n=1000$ chiavi: costruzione bottom-up $\Theta(n)$ e poi $1000$ removeMin, ciascuno con circa $\log_21000\approx10$ scambi al più.

Errori comuni

• Eseguire il bottom-up partendo dalla fine dell'array (le foglie sono già heap): si parte da $\lfloor n/2 \rfloor$.
• Percorrere $j$ in avanti nel bottom-up: il down-heap richiede che i sottoalberi siano già heap.
• Dire che il bottom-up costa $n \log n$ perché ogni down-heap è $\log n$: la somma dei costi per livello è lineare.
• Dimenticare il caso peggiore del top-down: array in ordine decrescente.