Esercizio 12inserimenti e rimozioni in uno heap

Richiami

Con indici da $1$: figli di $P[i]$ in $P[2i]$ e $P[2i+1]$, padre in $P[\lfloor i/2 \rfloor]$ (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 →).

• insert(k): $k$ in $P[\text{last}+1]$ poi up-heap: finché ha un padre con chiave maggiore, si scambia con il padre.
• removeMin(): si restituisce $P[1]$; si porta $P[\text{last}]$ in $P[1]$ e si accorcia di uno; poi down-heap: finché ha un figlio con chiave minore, si scambia con il figlio di chiave minima.

1. $P = [2, 5, 4, 9, 8, 7]$, insert(3)

        2
      /   \
     5     4
    / \   /
   9   8 7

$3$ va in posizione $7$, figlio destro di $P[3] = 4$. Padre $4 > 3$: scambio, $3$ sale in posizione $3$: $[2, 5, 3, 9, 8, 7, 4]$. Padre $P[1] = 2 < 3$: stop.

Risultato: $[2, 5, 3, 9, 8, 7, 4]$.

2. $P = [3, 6, 5, 10, 8, 12, 9]$, insert(4) poi removeMin()

Albero: radice $3$; figli $6, 5$; nipoti $10, 8$ (sotto $6$) e $12, 9$ (sotto $5$).

insert(4): $4$ in posizione $8$ (figlio sinistro di $P[4] = 10$). $10 > 4$: scambio, $4$ in posizione $4$: $[3, 6, 5, 4, 8, 12, 9, 10]$. Padre $P[2] = 6 > 4$: scambio, $4$ in posizione $2$: $[3, 4, 5, 6, 8, 12, 9, 10]$. Padre $P[1] = 3 < 4$: stop. Array dopo insert: $[3, 4, 5, 6, 8, 12, 9, 10]$.

removeMin(): si restituisce $3$. L'ultima entry ($10$) va in radice: $[10, 4, 5, 6, 8, 12, 9]$. Figli di $10$: $4$ e $5$, il minore è $4$: scambio $\to [4, 10, 5, 6, 8, 12, 9]$. Figli di $10$ in posizione $2$: $P[4] = 6$ e $P[5] = 8$, minore $6 < 10$: scambio $\to [4, 6, 5, 10, 8, 12, 9]$. In posizione $4$ non ci sono figli ($2 \cdot 4 = 8 > 7$).

Risultato: $[4, 6, 5, 10, 8, 12, 9]$.

3. $P = [2, 6, 4, 9, 8, 5, 7]$, removeMin()

Albero: radice $2$; figli $6, 4$; sotto $6$: $9, 8$; sotto $4$: $5, 7$. È un heap valido (ogni nodo $\le$ i figli).

Si restituisce $2$; l'ultima entry ($7$) va in radice: $[7, 6, 4, 9, 8, 5]$. Figli $6$ e $4$: minore $4$, scambio $\to [4, 6, 7, 9, 8, 5]$. Il $7$ è in posizione $3$ con figlio $P[6] = 5 < 7$ (non c'è $P[7]$): scambio $\to [4, 6, 5, 9, 8, 7]$. Posizione $6$ senza figli.

Risultato: $[4, 6, 5, 9, 8, 7]$.

4. $P = [5, 10, 7, 12, 11, 8]$, insert(3)

Albero: radice $5$; figli $10, 7$; sotto $10$: $12, 11$; sotto $7$: $8$. $3$ va in posizione $7$ (figlio destro di $P[3] = 7$). $7 > 3$: scambio $\to [5, 10, 3, 12, 11, 8, 7]$ ($3$ in posizione $3$). Padre $P[1] = 5 > 3$: scambio $\to [3, 10, 5, 12, 11, 8, 7]$ ($3$ in posizione $1$): radice, stop.

Risultato: $[3, 10, 5, 12, 11, 8, 7]$.

5. Sequenza di operazioni su heap vuoto

Ultimo passo: l'ultima entry ($6$) va in radice, $[6, 4, 3, 5, 7]$; figli $4, 3$: minore $3$, scambio $\to [3, 4, 6, 5, 7]$; in posizione $3$ non ci sono figli ($6 > 5$).

Albero finale: radice $3$; figli $4$ e $6$; sotto $4$: $5$ e $7$.

(Tutti gli array di questo esercizio sono stati verificati eseguendo un'implementazione dello heap.)

Errori comuni

• Nel down-heap scambiare con il figlio sinistro invece che con il minore tra i due.
• In removeMin portare in radice un'entry qualunque invece dell'ultima (si perde la completezza).
• Non fermare il down-heap quando $P[i] \le$ entrambi i figli, o proseguire oltre le foglie.
• Dimenticare di aggiornare $\text{last}$ (numero di entry) dopo insert/removeMin.