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

Top-down: $n-1$ 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.

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.

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

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

Bottom-up: dalle foglie verso la radice

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.

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.

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

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$: $[11, 9, 4, 13, 3, 7]$; $j = 2$: $[11, 3, 4, 13, 9, 7]$; $j = 1$: $[3, 9, 4, 13, 11, 7]$ ($11$ scende scambiando con $3$, poi con $9$).

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.

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

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.