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

In acest articol prezentam 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 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:

* va antreneaza mintea

* va veti putea descurca in situatii in care aveti nevoie de o structura de date similara dar nu la fel

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

* veti fi utilizatori informati ai bibliotecii STL

* veti intelege cand este bine sa folosoti o structura de date si cand nu
* veti avea avantajul de a sti precis de ce operatiile au anumite complexitati

* veti intelege cand este bine sa folositi o structura de date si cand nu
* veti avea avantajul de a sti precis de ce operatiile de baza au anumite complexitati

Acum ca avem o motivatie, sa studiem impreuna heap-urile.
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)$}.

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 nivelele sa fie complete, cu exceptia ultimului, care se completeaza incepand de la stanga si continuand pana la un 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.

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!

Partea cea mai frumoasa a acestui algoritm este ca el nu foloseste deloc memorie suplimentara. Iata explicatia: cand heap-ul are $N$ elemente, vom extrage maximul si il vom tine minte undeva in memorie. Pe de alta parte, in locul maximului (adica in radacina arborelui) trebuie adus ultimul element al vectorului, adica $H[N]$. Dupa aceasta operatie, heap-ul va avea $N-1$ noduri, al $N$-lea ramanand liber. Ce alt loc mai inspirat decat acest al $N$-lea nod ne-am putea dori pentru a stoca maximul? Practic, am interschimbat radacina, adica pe $H[1]$ cu $H[N]$. Acelasi lucru se face la fiecare pas, tinand cont de micsorarea permanenta a heap-ului.
==code(c) |

void heap_sort(Heap H, int N) {

void heapsort(Heap H, int N) {

    build_heap(H, N);
    // Sorteaza vectorul.