Esercizio 13costruzione di uno heap top-down e bottom-up

for j <- 2 to n do
    i <- j
    while (i > 1) AND (P[floor(i/2)].getKey() > P[i].getKey()) do
        swap(P[i], P[floor(i/2)])
        i <- floor(i/2)

---

1. Top-down: $P = [10, 8, 6, 7, 5, 2]$

Si tiene come heap il prefisso $P[1..j]$ e si fa salire $P[j]$ (vedi Costruzione di uno heapCostruire uno heap da un array di n entry: approccio top-down con n-1 insert, Theta(n log n); approccio bottom-up con down-heap dalle foglie verso la radice, Theta(n), con dimostrazione della somma; esempi svolti, in loco; unione di due alberi con heap-order.Costruzione di uno heap →).

Albero finale: radice $2$; figli $6$ e $5$; sotto $6$: $10$ e $7$; sotto $5$: $8$. È uno heap valido.

2. Bottom-up: $P = [11, 9, 7, 13, 3, 4]$

$n = 6$, $\lfloor n/2 \rfloor = 3$: si parte da $P[3]$ e si va fino a $P[1]$ con il down-heap.

Albero finale: radice $3$; figli $9$ e $4$; sotto $9$: $13$ e $11$; sotto $4$: $7$. Controllo: ogni nodo $\le$ i figli ✓.

3. Complessità del top-down

Limite superiore. L'iterazione $j$ esegue al più tante iterazioni del while quanti sono gli antenati di $P[j]$ nell'albero, cioè la profondità di $j$, pari a $\lfloor \log_2 j \rfloor \le \log_2 n$. Il costo di una iterazione è $O(\log j)$ (un numero costante di operazioni per scambio). Perciò

$$t(n) = O\Big(\sum_{j=2}^{n} \log_2 j\Big) \le O\big((n - 1) \log_2 n\big) = O(n \log n).$$

4. $n$ inserimenti in uno heap vuoto: $\Theta(n \log n)$

L'inserimento numero $j$ avviene su uno heap con $j - 1$ entry e costa al più $\lfloor \log_2 j \rfloor$ scambi più un numero costante di operazioni (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 →), quindi il totale è $O(n \log n)$ come sopra. Limite inferiore: se le chiavi sono inserite in ordine decrescente, ogni nuova chiave è minore di tutte quelle già presenti e sale fino alla radice, con $\lfloor \log_2 j \rfloor$ scambi. Il costo totale è almeno

$$\sum_{j=\lceil n/2 \rceil}^{n} \lfloor \log_2 j \rfloor \ \ge\ \frac{n}{2} \big\lfloor \log_2 \tfrac n2 \big\rfloor = \frac{n}{2}\big( \lfloor \log_2 n \rfloor - 1 \big) \in \Omega(n \log n),$$

perché sono almeno $\frac n2$ termini ciascuno $\ge \lfloor \log_2 \frac n2 \rfloor$. Essendo $O(n \log n)$ e $\Omega(n \log n)$, la complessità è $\Theta(n \log n)$ (al caso pessimo). Il bottom-up costruisce invece lo stesso heap da un array in $\Theta(n)$.

Errori comuni

• Nel bottom-up partire da $j = n$ o da $j = n/2 + 1$ (sono foglie) invece di $\lfloor n/2 \rfloor$; oppure procedere con $j$ crescente.
• Scambiare nel down-heap con il figlio sbagliato (si sceglie il minore dei due).
• Rispondere $O(n)$ al punto 3: è il costo del bottom-up; il top-down è $\Theta(n \log n)$.
• Nel limite inferiore dimenticare di indicare l'istanza cattiva (ordine decrescente).