Heap binomiale: differenze tra le versioni

Versione delle 12:11, 1 feb 2011

Versione delle 19:19, 1 feb 2011

Riga 1:

{{S|informatica}}

Un '''heap binomiale''' è un insieme di [[Albero binomiale|alberi binomiali]]. che soddisfa le seguenti proprietà:

# 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);,

==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 o 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ù <matH>lg(n)</math> radici, quindi la ricerca del minimo si può eseguire in <math>lg(n)</math> passi.

{{Portale|informatica}}