Heap binomiale: differenze tra le versioni

Versione delle 19:20, 1 feb 2011

Versione delle 19:24, 1 feb 2011

Riga 2:

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). Ciò significa anche che non possono esservi più di un albero binomiale con il medesimo grado,

# i nodi all'interno di ogni albero binomiale sonogode ordinatidella secondoproprietà di leordinamento regoleparziale degli [[heap]], (cioèossia laogni chiavenodo di unciascun nodoalbero è tale che la propria chiave sia sempre minoremaggiore o uguale della chiave deidel suoinodo figli)padre.

==Creazione di uno heap binomiale==

==Ricerca del minimo==

{{...}}

==Ricerca deldella minimochiave minima==

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.

==Unione di due heap binomiali==

{{...}}

==Inserimento di un nodo==

{{...}}

==Estrazione del nodo con chiave minima==

{{...}}

==Decremento di una chiave==

{{...}}

==Eliminazione di una chiave==

{{...}}

{{Portale|informatica}}