Heap binomiale: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m fix |
+ immagine |
||
Riga 4:
# 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,
# ogni albero binomiale gode della proprietà di ordinamento parziale degli [[heap]], ossia ogni nodo di ciascun albero è tale che la propria chiave sia sempre maggiore o uguale della chiave del nodo padre.
[[File:Binomial-heap-13.svg|thumb|right|300px|Esempio di heap binomiale costituito da 13 nodi con chiavi distinte. Lo heap è costituito da 3 [[albero binomiale|alberi binomiali di grado rispettivamente 0, 2 e 3]]
Gli heap binomiali appartengono alla classe di strutture dati definite come ''heap aggregabili'' ossia strutture dati di tipo heap che oltre alle consuete procedure di ricerca della chiave minima, inserimento di un nodo, estrazione del nodo con chiave minima ed eliminazione di una chiave (operazioni implementate ad esempio negli [[Heap binario|heap binari]], consentono anche l'implementazione dell'operazione di ''unione'' fra due heap che, a partire da due heap iniziali, restituisce un unico heap il cui insieme delle chiavi è pari all'unione degli insiemi delle chiavi dei due heap di partenza.
| |||