Esercizio 5

Descrivere a parole o con pseudocodice commentato l'operazione di estrazione del minimo nel caso di heap binomiali e di heap di Fibonacci.
Per ciascuno dei due casi, fornire un esempio concreto (mostrando tutte le fasi dell'operazione) di estrazione del minimo da uno heap di 13 elementi, che causi modifiche a tutti gli alberi presenti nella struttura dati.

Ci limitiamo a parlare dell'esempio concreto. Ricordiamo che uno heap binomiale ha ``forma'' obbligata, ovvero dal numero di elementi possiamo risalire univocamente alle dimensioni dei singoli alberi binomiali che lo compongono. Lo heap in oggetto dovrà dunque avere tre alberi: uno da $8$, uno da $4$, uno da $1.$ Se il minimo fosse contenuto nell'albero piú piccolo, eliminando quest'ultimo saremmo già posto. Se fosse contenuto in quello da $4$, questo si spezzerebbe in $2+1$ e potrebbe venir ricomposto, assieme all'albero da $1$ che sopravvive, con una fusione dei due alberi da uno, cosicché si avrebbero a quel punto due alberi da $2$ a loro volta fusi in un albero da $4$. Tutto questo senza toccare l'albero da $8$. Nell'esempio il minimo dovrà dunque risiedere nell'albero da $8$. Con l'estrazione, esso viene smembrato in $4+2+1.$ Ora i vecchi alberi da $1$ e da $4$ sono affiancati entrambi da alberi dello stesso tipo; questo basta a garantire che saranno soggetti a fusione, e che quindi alla fine ogni albero sarà stato toccato.

Nel caso degli heaps di Fibonacci, ricordiamo che il layout degli alberi prima dell'estrazione può essere molto più vario. Dopo l'estrazione, comunque, grazie all'operazione di consolidamento, avremo le forme tipiche degli heaps binomiali e quindi, nel nostro caso, ancora una volta un albero da $8$ e uno da $4.$

Un esempio molto sbrigativo è quello dove partiamo da tredici nodi radice, ad esempio prodotti da tredici inserzioni successive. Se dopo tali inserzioni viene effettuata un'estrazione di minimo, avviene la consolidate che, raggruppando i nodi in $8+4,$ ovviamente li tocca tutti.