Heap binomial

Exemplu de heap binomial format din 13 noduri cu chei distincte. Heapul este format din 3 arbori binomiali de grad 0, 2 și respectiv 3

O grămadă binomială este un set de arbori binomiali care îndeplinește următoarele proprietăți:

pentru orice întreg $k$ ${\ displaystyle k}$ $k$ non-negativ, există cel mult un arbore binomial a cărui rădăcină are grad $k$ ${\ displaystyle k}$ $k$ (s-ar putea să nu existe nici măcar). Aceasta înseamnă, de asemenea, că nu poate exista mai mult de un arbore binomial cu același grad,
fiecare arbore binomial are proprietatea ordonării parțiale a grămezilor , adică fiecare nod al fiecărui arbore este astfel încât cheia sa este întotdeauna mai mare sau egală cu cheia nodului părinte.

Grămezile binomiale aparțin clasei de structuri de date definite ca grămezi agregabile, adică structuri de date tip heap care, pe lângă procedurile obișnuite pentru căutarea cheii minime, inserarea unui nod, extragerea nodului cu o cheie minimă și eliminarea unei chei (operațiile implementate de exemplu în grămezi binare ), permit, de asemenea, implementarea operației de unire între două grămezi care, pornind de la două grămezi inițiale, returnează o singură grămadă al cărei set de chei este egal cu unirea seturilor de chei ale celor două grămezi de plecare.

Crearea unei grămezi binomiale

Procedura de creare returnează o grămadă binomială goală și necesită timp pentru executare $\Theta (1)$ ${\ displaystyle \ Theta (1)}$ ${\ displaystyle \ Theta (1)}$ . Pointerul head [H] va indica capul listei rădăcinii heap.

 Make-Heap ()
     creează H și îi atribuie spațiu de memorie
     cap [H] ← NIL
     întoarcere H

Căutați cheia minimă

Fiecare arbore binomial care alcătuiește o grămadă binomială are proprietatea de sortare parțială a grămezilor, deci fiecare dintre ele va avea cheia minimă la rădăcină. Cheia minimă a heap-ului binomial va fi așadar conținută într-unul din nodurile rădăcină ale diferiților arbori binomiali care o constituie, în consecință căutarea cheii minime este redusă la o căutare a minimului în lista rădăcinilor binomului copaci. Numărul maxim de rădăcini arborelui binomial al unei grămezi binomiale este cel mult $\lfloor \log n\rfloor +1$ ${\ displaystyle \ lfloor \ log n \ rfloor +1}$ ${\ displaystyle \ lfloor \ log n \ rfloor +1}$ de aceea timpul pentru efectuarea percheziției este $O(\log n)$ ${\ displaystyle O (\ log n)}$ $O (\ log n)$ .

Unirea a două grămezi binomiale

Deoarece un arbore binomial, prin definiția sa, conține exact $2^{k}$ ${\ displaystyle 2 ^ {k}}$ $2 ^ {k}$ noduri în interiorul acestuia, cu $k$ ${\ displaystyle k}$ $k$ gradul arborelui, deducem că o grămadă binomială poate conține orice număr de noduri în interiorul ei, alcătuind arbori binomiali de grade diferite, exact așa cum o cifră binară este exprimată în funcție de diferitele puteri de 2. Suma a două grămezi binomiale apare exact ca suma a două numere binare, unde a $1$ ${\ displaystyle 1}$ $1$ la loc $k$ ${\ displaystyle k}$ $k$ indică prezența unui arbore de grad $k$ ${\ displaystyle k}$ $k$ în interiorul structurii. Heapul binomial rezultat va avea în consecință aceeași structură ca numărul zecimal rezultat al sumei.

 Uniune (H1, H2)
     Creez o nouă listă care conține toți arborii binomiali ai H1 și H2 sortați după grade
     Pentru fiecare arbore x din listă:
        next <- next [x];
        frate <- următorul [următor];
        if (rang [x] == rang [următor])
           if (rang [următor] == rang [frate])
              merge (următor, frate);
           altceva
              merge (x, următor);
        x <- următor;

Merge (H1, H2)
     Plasez H2 ca un copil al rădăcinii H1

Algoritmul uniunii creează o listă dinamică unică care conține toți arborii binomiali sortați în funcție de grad crescător. Apoi, parcurge fiecare element (care va fi rădăcina unui arbore binomial), urmărind următoarele două elemente.

Introducerea unui nod

Operațiunea de inserare a unui nod într-un heap binomial constă în crearea unui nou heap binomial format doar din nodul de inserat (cu timpul de execuție $O(1)$ ${\ displaystyle O (1)}$ $O (1)$ ) și într-o operație ulterioară de alăturare heap-ului binomial original cu heap-ul binomial nou creat (operație care necesită timp de execuție $O(\log n)$ ${\ displaystyle O (\ log n)}$ $O (\ log n)$ ). Prin urmare, timpul total de execuție este $O(\log n)$ ${\ displaystyle O (\ log n)}$ $O (\ log n)$ .

Extragerea minimă a nodului cheii

Operațiunea de extragere a nodului cheie minim elimină nodul cheie minim din heap-ul binomial prin returnarea indicatorului său. Această procedură constă din trei etape și să presupunem că indicăm cu $H.$ ${\ displaystyle H}$ $H.$ grămada binomială de pornire:

căutați rădăcina cu cheia minimă și ștergeți-o din lista rădăcină a arborelui binomial,
se creează o nouă grămadă goală ${H.}^{'}$ ${\ displaystyle H '}$ ${\ displaystyle H '}$ ,
lista copiilor rădăcinii șterse anterior este inversată și indicatorul către primul nod obținut este considerat capul noii liste de rădăcini,
în cele din urmă, se efectuează operația de îmbinare a grămezilor $H.$ ${\ displaystyle H}$ $H.$ Și ${H.}^{'}$ ${\ displaystyle H '}$ ${\ displaystyle H '}$ .

Procedura necesită timp pentru finalizare $O(\log n)$ ${\ displaystyle O (\ log n)}$ $O (\ log n)$ .

Decrementarea unei chei

Operația de decrementare a unei chei constă în suprascrierea valorii nodului cu o valoare nouă, strict mai mică. Prin urmare, dat o grămadă binomială $H.$ ${\ displaystyle H}$ $H.$ , indicatorul $X$ ${\ displaystyle x}$ $X$ la nodul de modificat și la noua cheie $k$ ${\ displaystyle k}$ $k$ a fi inserat în $X$ ${\ displaystyle x}$ $X$ , procedura cuprinde 3 faze:

verifică dacă valoarea $k$ ${\ displaystyle k}$ $k$ este strict mai mică decât valoarea cheie prezentă în prezent în nod $X$ ${\ displaystyle x}$ $X$ ,
valoarea cheii nodului este suprascrisă $X$ ${\ displaystyle x}$ $X$ cu valoarea $k$ ${\ displaystyle k}$ $k$ ,
folosind două indicatoare $y$ ${\ displaystyle y}$ $y$ Și $z$ ${\ displaystyle z}$ $z$ care inițial indică nodul $X$ ${\ displaystyle x}$ $X$ și la nodul părinte al $X$ ${\ displaystyle x}$ $X$ , apare dacă cheia nodului $X$ ${\ displaystyle x}$ $X$ este mai mic decât cheia nodului $z$ ${\ displaystyle z}$ $z$ iar în acest caz se schimbă cheile celor două noduri. După schimbarea indicatoarelor $y$ ${\ displaystyle y}$ $y$ Și $z$ ${\ displaystyle z}$ $z$ sunt actualizate și vor indica spre vechiul nod indicat de respectiv $z$ ${\ displaystyle z}$ $z$ și la nodul părinte al $z$ ${\ displaystyle z}$ $z$ . Acest pas se repetă până când condiția cheie de inegalitate nu mai este satisfăcută sau până când $z$ ${\ displaystyle z}$ $z$ indică o locație de memorie nulă.

Procedura necesită timp pentru finalizare $O(\log n)$ ${\ displaystyle O (\ log n)}$ $O (\ log n)$ .

Ștergerea unei taste

Operația de ștergere a unei chei (fără a returna un pointer la ea) constă din două faze:

este redus la valoarea minimă care poate fi reprezentată prin calcularea valorii cheii de eliminat,
extrage cheia cu valoare minimă din heap-ul binomial.

Cele două operații necesită timp de execuție $O(\log n)$ ${\ displaystyle O (\ log n)}$ $O (\ log n)$ prin urmare, timpul total de execuție este întotdeauna $O(\log n)$ ${\ displaystyle O (\ log n)}$ $O (\ log n)$ .

Bibliografie

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introducere în algoritmi . Jackson Books, 2003, ISBN 88-256-1421-7 .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe heap binomial

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

V · D · M Structuri de date
Tipuri	Colecție · Container
Abstract	Matrice asociativă ( Multimap ) · Listă · Stivă · Coadă ( Deque ) · prioritate coadă · Septembrie ( multiset · disjoint-set )
Matrice	Matrice de biți · Tampon circular · Matrice dinamică · Masă Hash · Matrice rar
Conectați	Lista asociațiilor · Lista Linked · Lista Omite · desfășură lista inlantuita · XOR listă înlănțuită
Copaci	B-tree · binar de căutare Arbore ( Arbore AA · Arbore AVL · arbore rosu-negru · binar de căutare copac echilibrat · copac evazat ) · Heap ( Heap binar · binom Heap · Heap Fibonacci ) · Merkle copac · copac SPQR · Arbore PQ · Binar copac indexat
Grafice	Diagrama binară de decizie · Digraf aciclic · Automat finic deterministic aciclic
Împărțirea copacilor informație spatiala	Copac Quadrament · M-tree · R-arbore ( R * arbore · R + copac ) · X-tree
Lista structurilor de date