Heap binomiale: differenze tra le versioni

Versione delle 21:12, 21 dic 2010

Versione delle 12:11, 1 feb 2011

Riga 1:

{{S|informatica}}

Un '''heap binomiale''' è un insieme di [[alberi binomiali]].

==Definizione==

Un '''heap binomiale''' per essere tale deve soddisfare le seguenti regole:

# per qualsiasi intero <math>k</matH> non negativo esiste al più un albero binomiale la cui radice ha grado <math>k</math> (può anche non esserci);

# i nodi all'interno di ogni albero binomiale sono ordinati secondo le regole degli [[heap]] (cioè la chiave di un nodo è sempre ≤minore allao uguale della chiave dei suoi figli).

==Ricerca del minimo==

Essendo lo heap binomiale rappresentabile come una lista concatenata di alberi binomiali e tenendo conto che ogni albero binomiale ha come radice la sua chiave minima si può facilmente intuire che dato un insieme di <math>n</math> chiavi, uno heap binomiale avrà al più log<matH>lg(n)</math> radici, quindi la ricerca del minimo si può eseguire in log<math>lg(n)</math> passi.

{{Portale|informatica}}