(Categoria _Structuri de date_, Autor _Catalin Francu_, Versiunea originala preluata din cartea _"Psihologia concursurilor de informatica"_)

(toc){width: 20em}*{text-align:center;} *Continut*

(toc){width: 30em}*{text-align:center;} *Continut*

* 'Definirea notiunii de _heap_':heapuri#definire
* 'Structura de heap si metode ajutatoare':heapuri#structura
* 'Cautarea maximului':heapuri#cautarea-maximului

* 'Alternative STL':heapuri#stl
* 'Aplicatii':heapuri#aplicatii

In acest articol vom prezenta structura de date numita $heap$, cum poate fi aceasta implementata precum si alternative STL. Desi este putin probabil sa ajungeti sa implementati heap-urile de la "zero" daca stiti STL, consideram ca prezentarea acestora nu este de prisos. Aici atingem problema mai generala a "de ce trebuie sa inteleg X (poate fi vorba de un algoritm, o structura de date, s.a.m.d.) daca il am deja implementat?". Iata cateva motive:

In acest articol vom prezenta structura de date numita $heap$, cum poate fi aceasta implementata, precum si alternative STL. Desi este putin probabil sa ajungeti sa implementati heap-urile de la "zero" daca stiti STL, consideram ca prezentarea acestora nu este de prisos. Aici atingem problema mai generala "de ce trebuie sa inteleg X (poate fi vorba de un algoritm, o structura de date, s.a.m.d.) daca il am deja implementat?". Iata cateva motive:

* va antreneaza mintea
* va veti putea descurca in situatii in care aveti nevoie de o structura de date asemanatoare, dar nu la fel

h2(#definire). Definirea notiunii de _heap_

Un heap (engl. _gramada_) este un vector care poate fi privit si ca un arbore binar, asa cum se vede in figura de mai jos:

Un heap ({_engl._} gramada) este un vector care poate fi privit si ca un arbore binar, asa cum se vede in figura de mai jos:

!heapuri?heap.JPG!
Langa fiecare nod din arbore se afla cate un numar, reprezentand pozitia in vector pe care ar avea-o nodul respectiv. Pentru cazul considerat, vectorul echivalent ar fi {$H = (12 10 11 10 7 9 3 2 8 1 4 3)$}.

Se observa ca nodurile sunt parcurse de la stanga la dreapta si de sus in jos. O proprietate necesara pentru ca un arbore binar sa se poata numi heap este ca toate nivelurile sa fie complete, cu exceptia ultimului, care se completeaza incepand de la stanga si continuand pana la un anume punct. De aici deducem ca inaltimea unui heap cu $N$ noduri este <tex> h=[\log_2 N] </tex> (reamintim ca inaltimea unui arbore este adancimea maxima a unui nod, considerand radacina drept nodul de adancime 0). Reciproc, numarul de noduri ale unui heap de inaltime $h$ este <tex> N\in [2^h, 2^{h+1}-1]</tex>.

Se observa ca nodurile sunt parcurse de la stanga la dreapta si de sus in jos. O proprietate necesara pentru ca un arbore binar sa se poata numi $heap$ este ca toate nivelurile sa fie complete, cu exceptia ultimului, care se completeaza incepand de la stanga si continuand pana la un anume punct. De aici deducem ca inaltimea unui heap cu $N$ noduri este <tex> h=[\log_2 N] </tex> (reamintim ca inaltimea unui arbore este adancimea maxima a unui nod, considerand radacina drept nodul de adancime $0$). Reciproc, numarul de noduri ale unui heap de inaltime $h$ este <tex> N\in [2^h, 2^{h+1}-1]</tex>.

Tot din aceasta organizare mai putem deduce ca tatal unui nod $k > 1$ este nodul $[k/2]$, iar fiii nodului k sunt nodurile $2k$ si $2k+1$. Daca $2k = N$, atunci nodul $2k+1$ nu exista, iar nodul $k$ are un singur fiu; daca $2k > N$, atunci nodul $k$ este frunza si nu are nici un fiu. Exemple: tatal nodului 5 este nodul 2, iar fiii sai sunt nodurile 10 si 11. Tatal nodului 6 este nodul 3, iar unicul sau fiu este nodul 12. Tatal nodului 9 este nodul 4, iar fii nu are, fiind frunza in heap.

Tot din aceasta organizare mai putem deduce ca tatal unui nod $k > 1$ este nodul $[k/2]$, iar fiii nodului $k$ sunt nodurile $2k$ si $2k+1$. Daca $2k = N$, atunci nodul $2k+1$ nu exista, iar nodul $k$ are un singur fiu; daca $2k > N$, atunci nodul $k$ este frunza si nu are niciun fiu. Exemple: tatal nodului $5$ este nodul $2$, iar fiii sai sunt nodurile $10$ si $11$. Tatal nodului $6$ este nodul $3$, iar unicul sau fiu este nodul $12$. Tatal nodului $9$ este nodul $4$, iar fii nu are, fiind frunza in heap.

Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de aflarea a maximului, este aceea ca valoarea oricarui nod este mai mare sau egala cu valoarea oricarui fiu al sau. Dupa cum se vede mai sus, nodul 2 are valoarea 10, iar fiii sai - nodurile 4 si 5 - au valorile 10 si respectiv 7. Intrucat operatorul ≥ este tranzitiv, putem trage concluzia ca un nod este mai mare sau egal decat oricare din nepotii sai si, generalizand, va rezulta ca orice nod este mai mare sau egal decat toate nodurile din subarborele a carui radacina este el.

Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de aflarea a maximului, este aceea ca valoarea oricarui nod este mai mare sau egala cu valoarea oricarui fiu al sau. Dupa cum se vede mai sus, nodul $2$ are valoarea $10$, iar fiii sai - nodurile $4$ si $5$ - au valorile $10$ si respectiv $7$. Intrucat operatorul $≥$ este tranzitiv, putem trage concluzia ca un nod este mai mare sau egal decat oricare din nepotii sai si, generalizand, va rezulta ca orice nod este mai mare sau egal decat toate nodurile din subarborele a carui radacina este.

Aceasta afirmatie nu decide in nici un fel intre valorile a doua noduri dispuse astfel incat nici unul nu este descendent al celuilalt. Cu alte cuvinte, nu inseamna ca orice nod de pe un nivel mic are valoare mai mare decat nodurile mai apropiate de frunze. Este cazul nodului 7, care are valoarea 3 si este mai mic decat nodul 9 de valoare 8, care este totusi asezat ma jos in heap. In orice caz, o prima concluzie care rezulta din aceasta proprietate este ca radacina are cea mai mare valoare din tot heap-ul.

Aceasta afirmatie nu decide in niciun fel intre valorile a doua noduri dispuse astfel incat niciunul nu este descendent al celuilalt. Cu alte cuvinte, nu inseamna ca orice nod de pe un nivel mic are valoare mai mare decat nodurile mai apropiate de frunze. Este cazul nodului $7$, care are valoarea $3$ si este mai mic decat nodul $9$ de valoare $8$, nod asezat totusi mai jos in heap. In orice caz, o prima concluzie care rezulta din aceasta proprietate este ca radacina are cea mai mare valoare din tot heap-ul.

Structura de heap permite efectuarea multor operatii intr-un timp foarte bun:

* Inserarea unui element in $O(log N)$
* Sortarea elementelor din heap in $O(N log N)$

Mentionam ca operatia de cautarea a unui element are complexitatea $O(N)$ dar, de obicei, heap-ul nu este folosit cand acest tip de operatii este frecvent.

Mentionam ca operatia de cautare a unui element are complexitatea $O(N)$ dar, de obicei, heap-ul nu este folosit cand acest tip de operatii este frecvent.

Desigur, toate aceste operatii se fac mentinand permanent structura de heap a arborelui, adica respectand modul de repartizare a nodurilor pe nivele si plasarea mai sus a elementelor de valoare mai mare. Este de la sine inteles ca datele nu se vor reprezenta in memorie in forma arborescenta, ci in cea vectoriala.

Precizam de asemenea ca heap-ul poate fi organizat si pe baza operatorului de $≤$. In acest caz, in varful heap-ului vom avea minimul dintre elementele pastrate in heap. In functie de operatorul folosit, putem numi structura de date max-heap sau min-heap. In continuare vom prezenta operatiile intr-un max-heap, adaptarea lor pentru min-heap-uri fiind usoara.

Precizam de asemenea ca heap-ul poate fi organizat si pe baza operatorului de $≤$. In acest caz, in varful heap-ului vom avea minimul dintre elementele pastrate in heap. In functie de operatorul folosit, putem numi structura de date $max-heap$ sau $min-heap$. In continuare vom prezenta operatiile intr-un max-heap, adaptarea lor pentru min-heap-uri fiind usoara.

h2(#structura). Structura de heap si metode ajutatoare

h2(#creare-heap). Crearea unei structuri de heap dintr-un vector oarecare

Pentru a discuta acest aspect, vom vorbi mai intai despre doua proceduri specifice heap-urilor, $sift$ (engl. _a cerne_) si $percolate$ (engl. _a se infiltra_). Sa presupunem ca un vector are o structura de heap, cu exceptia unui nod care este mai mic decat unul din fiii sai. Este cazul nodului 3 din figura de mai jos, care are o valoare mai mica decat fii sai (nodurile 6 si 7):

Pentru a discuta acest aspect, vom vorbi mai intai despre doua proceduri specifice heap-urilor, $sift$ ({_engl._} a cerne) si $percolate$ ({_engl._} a se infiltra). Sa presupunem ca un vector are o structura de heap, cu exceptia unui nod care este mai mic decat unul din fiii sai. Este cazul nodului 3 din figura de mai jos, care are o valoare mai mica decat fii sai (nodurile 6 si 7):

!heapuri?create1.JPG!