heap binomiale

Un heap binomiale è un insieme di alberi binomiali che soddisfa le seguenti proprietà: 1. * per qualsiasi intero non negativo esiste al più un albero binomiale la cui radice ha grado (può anche non esserci). Ciò significa anche che non possono esservi più di un albero binomiale con il medesimo grado, 2. * 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. 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 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.