Heap binomiale

Un heap binomiale è un insieme di alberi binomiali che soddisfa le seguenti proprietà:

1. per qualsiasi intero ${\displaystyle k}$ non negativo esiste al più un albero binomiale la cui radice ha grado ${\displaystyle k}$ (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.

Creazione di uno heap binomiale

La procedura di creazione restituisce uno heap binomiale vuoto e richiede tempo di esecuzione ${\displaystyle \Theta (1)}$ .

Ricerca della chiave minima

Ogni albero binomiale che costituisce uno heap binomiale gode della proprietà di ordinamento parziale degli heap, pertanto ognuno di essi avrà la chiave minima in corrispondenza della radice. La chiave minima dello heap binomiale sarà, quindi, contenuta, in uno dei nodi radice dei vari alberi binomiali che lo costituiscono, di conseguenza la ricerca della chiave minima si riduce ad una ricerca del minimo nella lista delle radici degli alberi binomiali. Il numero massimo di radici di alberi binomiali di uno heap binomiale è al più ${\displaystyle \lfloor lgn\rfloor +1}$  dunque il tempo per l'esecuzione della ricerca è ${\displaystyle O(lgn)}$ 

Unione di due heap binomiali

Inserimento di un nodo

L'operazione di inserimento di un nodo in uno heap binomiale consiste nella creazione di un nuovo heap binomiale costituito solo dal nodo da inserire (con tempo di esecuzione ${\displaystyle O(1)}$ ) e in una successiva operazione di unione dello heap binomiale originale con lo heap binomiale appena creato (operazione che richiede tempo di esecuzione ${\displaystyle O(lgn)}$ ). Il tempo complessivo di esecuzione è pertanto ${\displaystyle O(lgn)}$ .

Estrazione del nodo con chiave minima

L'operazione di estrazione del nodo con chiave minima prevede l'eliminazione dallo heap binomiale del nodo con chiave minima restituendone il puntatore. Tale procedura consta di tre fasi e si supponga di indicare con ${\displaystyle H}$  lo heap binomiale di partenza:

1. si cerca la radice con la chiave minima e la si elimina dalla lista delle radici degli alberi binomiali,
2. si crea un nuovo heap vuoto ${\displaystyle H'}$ ,
3. si inverte la lista dei figli della radice precedentemente eliminata e si considera come testa della nuova lista delle radici il puntatore al primo nodo ottenuto,
4. si effettua, infine, l'operazione di unione tra gli heap ${\displaystyle H}$  e ${\displaystyle H'}$ .

La procedura impiega tempo di esecuzione ${\displaystyle O(lgn)}$ .

Decremento di una chiave

Eliminazione di una chiave

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica