== include(page="template/todo") ==

In acest articol prezentam structura de date numita Heap si cum poate fi implementat sau evitat folosind STL ({$priority_queue<>$} si {$set<>$}). Desi este putin probabil ca un programator C++ ce cunoaste STL sa ajunga sa implementeze heap-urile de la "zero" consideram ca prezentarea heap-urilor nu este de prisos deoarece este importanta intelegerea functionarii unei structuri de date inainte de folosirea ei, chiar si implementata de-a gata. O motivatie in plus pentru un astfel de articol este faptul ca programatorii in Pascal nu dispun, din pacate, de ceva echivalent STL-ului *TODO: pentru asta ar cam trebui sa bagam pseudocod in locul snippet-urilor de cod C++ :D*

In acest articol prezentam structura de date numita heap si cum poate fi aceasta implementata sau evitata folosind STL ({$priority_queue<>$} si {$set<>$}). Desi este putin probabil ca un programator C++ ce cunoaste STL sa ajunga sa implementeze heap-urile de la "zero" consideram ca prezentarea heap-urilor nu este de prisos deoarece este importanta intelegerea functionarii unei structuri de date inainte de folosirea ei, chiar si implementata de-a gata. O motivatie in plus pentru un astfel de articol este faptul ca programatorii in Pascal nu dispun, din pacate, de ceva echivalent STL-ului.

h2. Definirea notiunii de _heap_

!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^n, 2^{n+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.

Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de cautare, 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 minimului/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.

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.