Movatterモバイル変換


[0]ホーム

URL:


Vai al contenuto
WikipediaL'enciclopedia libera
Ricerca

Heap binomiale

Da Wikipedia, l'enciclopedia libera.
Niente fonti!
Questa voce o sezione sull'argomento programmazionenon cita le fonti necessarie o quelle presenti sono insufficienti.
Abbozzo
Questa voce sull'argomento programmazione è solo unabbozzo.
Contribuisci a migliorarla secondo leconvenzioni di Wikipedia.
Esempio di heap binomiale costituito da 13 nodi con chiavi distinte. Lo heap è costituito da 3alberi binomiali di grado rispettivamente 0, 2 e 3

Unheap binomiale è un insieme dialberi binomiali che soddisfa le seguenti proprietà:

  1. per qualsiasi interok{\displaystyle k} non negativo esiste al più un albero binomiale la cui radice ha gradok{\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 degliheap, 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 comeheap 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 negliheap binari), consentono anche l'implementazione dell'operazione diunione 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.

Creazione di uno heap binomiale

[modifica |modifica wikitesto]

La procedura di creazione restituisce uno heap binomiale vuoto e richiede tempo di esecuzioneΘ(1){\displaystyle \Theta (1)}. Il puntatorehead[H] punterà alla testa della lista delle radici dello heap.

  Make-Heap()     crea H ed assegna ad esso spazio di memoria     head[H] ← NIL     return H

Ricerca della chiave minima

[modifica |modifica wikitesto]

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ùlogn+1{\displaystyle \lfloor \log n\rfloor +1} dunque il tempo per l'esecuzione della ricerca èO(logn){\displaystyle O(\log n)}.

Unione di due heap binomiali

[modifica |modifica wikitesto]

Dato che un albero binomiale, per sua definizione, contiene esattamente2k{\displaystyle 2^{k}} nodi al suo interno, conk{\displaystyle k} grado dell'albero, deduciamo che uno heap binomiale possa contenere un qualsiasi numero di nodi al suo interno, componendo alberi binomiali di gradi diversi, esattamente come una cifra binaria è espressa in funzione delle diverse potenze di 2.La somma di due heap binomiali avviene esattamente come la somma tra due numeri binari, dove un1{\displaystyle 1} in posizionek{\displaystyle k} indica la presenza di un albero di gradok{\displaystyle k} all'interno della struttura. Lo heap binomiale risultante avrà di conseguenza la stessa struttura del numero decimale risultato della somma.

  Union(H1, H2)     Creo una nuova lista contenente tutti gli alberi binomiali di H1 e H2 ordinati per grado     Per ogni albero x della lista:        next <- next[x];        sibling <- next[next];        if(rank[x] == rank[next])           if(rank[next] == rank[sibling])              merge(next, sibling);           else              merge(x, next);        x <- next;
  Merge(H1, H2)     Pongo H2 come figlio della radice di H1

L'algoritmo di unione crea un'unica lista dinamica contenente tutti gli alberi binomiali ordinati per grado crescente.Dopodiché scorre ogni elemento (che sarà la radice di un albero binomiale) osservando i suoi due elementi successivi.

Inserimento di un nodo

[modifica |modifica wikitesto]

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 esecuzioneO(1){\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 esecuzioneO(logn){\displaystyle O(\log n)}). Il tempo complessivo di esecuzione è pertantoO(logn){\displaystyle O(\log n)}.

Estrazione del nodo con chiave minima

[modifica |modifica wikitesto]

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 conH{\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 vuotoH{\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 heapH{\displaystyle H} eH{\displaystyle H'}.

La procedura impiega tempo di esecuzioneO(logn){\displaystyle O(\log n)}.

Decremento di una chiave

[modifica |modifica wikitesto]

L'operazione di decremento di una chiave consiste nel sovrascrivere il valore del nodo con un nuovo valore strettamente minore. Quindi, dato un heap binomialeH{\displaystyle H}, il puntatorex{\displaystyle x} al nodo da modificare e la nuova chiavek{\displaystyle k} da inserire inx{\displaystyle x}, la procedura consta di 3 fasi:

  1. si verifica che il valorek{\displaystyle k} sia strettamente minore del valore della chiave attualmente presente nel nodox{\displaystyle x},
  2. si sovrascrive il valore della chiave del nodox{\displaystyle x} con il valorek{\displaystyle k},
  3. utilizzando due puntatoriy{\displaystyle y} ez{\displaystyle z} che inizialmente puntano al nodox{\displaystyle x} e al nodo padre dix{\displaystyle x}, si verifica se la chiave del nodox{\displaystyle x} è minore della chiave del nodoz{\displaystyle z} e in tal caso si scambiano le chiavi dei due nodi. Dopo lo scambio i puntatoriy{\displaystyle y} ez{\displaystyle z} vengono aggiornati e punteranno rispettivamente al vecchio nodo puntato daz{\displaystyle z} e al nodo padre diz{\displaystyle z}. Questa fase viene ripetuta fino a quando la condizione di disuguaglianza delle chiavi non viene più soddisfatta o fino a quandoz{\displaystyle z} punta ad una locazione di memoria nulla.

La procedura impiega tempo di esecuzioneO(logn){\displaystyle O(\log n)}.

Eliminazione di una chiave

[modifica |modifica wikitesto]

L'operazione di eliminazione di una chiave (senza che ne venga restituito un puntatore) consiste in due fasi:

  1. si decrementa al minimo valore rappresentabile dal calcolare il valore della chiave da eliminare,
  2. si estrae la chiave con valore minimo dallo heap binomiale.

Le due operazioni richiedono rispettivamente tempo di esecuzioneO(logn){\displaystyle O(\log n)} pertanto il tempo di esecuzione complessivo è sempreO(logn){\displaystyle O(\log n)}.

Bibliografia

[modifica |modifica wikitesto]
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,Introduzione agli algoritmi. Jackson Libri, 2003,ISBN 88-256-1421-7.

Altri progetti

[modifica |modifica wikitesto]

Altri progetti

V · D · M
Strutture dati
TipiCollezione ·Container
AstratteArray associativo (Multimap) ·Lista ·Pila ·Coda (Deque) ·Coda di priorità ·Set (Multiset ·Mfset)
ArrayBit array ·Buffer circolare ·Array dinamico ·Hash table ·Array sparso
CollegateLista di associazioni ·Lista concatenata ·Skip list ·Unrolled linked list ·Lista concatenata tramite XOR
AlberiB-albero ·Albero binario di ricerca (Albero AA ·Albero AVL ·RB-Albero ·Albero binario di ricerca bilanciato ·Albero splay) ·Heap (Heap binario ·Heap binomiale ·Heap di Fibonacci) ·Albero di Merkle ·Albero SPQR ·Albero PQ ·Albero indicizzato binario
GrafiDiagramma binario di decisione ·Digrafo aciclico ·Automa a stati finiti deterministico aciclico
Alberi di partizionamento
dei dati spaziali
Albero quadramentale ·M-tree ·R-tree (R* tree ·R+ tree) ·X-tree
Lista di strutture dati
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica
Estratto da "https://it.wikipedia.org/w/index.php?title=Heap_binomiale&oldid=133066783"
Categoria:
Categorie nascoste:

[8]ページ先頭

©2009-2025 Movatter.jp