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

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 a 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 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*

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 de ducem 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>.

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.

}
==

Acum ne putem ocupa efectiv de construirea unui heap. Am spus ca procedura Sift presupune ca ambii fii ai nodului pentru care este ea apelata au structura de heap. Aceasta inseamna ca putem  apela procedura Sift pentru orice nod imediat superior nivelului frunzelor, deoarece frunzele sunt arbori cu un singru nod, si deci heap-uri corecte. Apeland procedura Sift pentru toate nodurile de deasupra frunzelor, vom obtine deja o structura mai organizata, asigurandu-ne ca pe ultimele doua nivele avem de-a face numai cu heap-uri. Apoi apelam aceeasi procedura pentru nodurile de pe al treilea nivel incepand de la frunze, apoi pentru cele de deasupra lor si asa mai departe pana ajungem la radacina. In acest moment, heap-ul este construit. Iata cum functioneaza algoritmul pentru un arbore total dezorganizat:

Acum ne putem ocupa efectiv de construirea unui heap. Am spus ca procedura Sift presupune ca ambii fii ai nodului pentru care este ea apelata au structura de heap. Aceasta inseamna ca putem apela procedura Sift pentru orice nod imediat superior nivelului frunzelor, deoarece frunzele sunt arbori cu un singru nod, si deci heap-uri corecte. Apeland procedura Sift pentru toate nodurile de deasupra frunzelor, vom obtine deja o structura mai organizata, asigurandu-ne ca pe ultimele doua nivele avem de-a face numai cu heap-uri. Apoi apelam aceeasi procedura pentru nodurile de pe al treilea nivel incepand de la frunze, apoi pentru cele de deasupra lor si asa mai departe pana ajungem la radacina. In acest moment, heap-ul este construit. Iata cum functioneaza algoritmul pentru un arbore total dezorganizat:

!heapuri?create5.JPG!

* Este o aplicatie teoretica/fortata
* Mareste prea mult articolul

*Feedback (Stefan):* As sugera transformarea problemei intr-una mai utila si mai putin fortata: Sa se interclaseze in mod eficient $K$ vectori sortati.
 

h2. Problema
Sperand ca am reusit sa explicam modul de functionare al unui heap, .

Chiar faptul ca ni se cere o complexitate de ordinul $O(N*log k)$ ne sugereaza construirea unui heap cu $O(k)$ noduri. Sa ne inchipuim ca am construi un heap $H$ format din primele $k+1$ elemente ale vectorului $V$.  Diferenta fata de ce am spus pana acum este ca orice nod va trebui sa fie mai mic decat fiii sai. Acest heap va servi deci la extragerea minimului.

Deoarece vectorul este $k-sortat$, rezulta ca elementul care s-ar gasi pe prima pozitie in vectorul sortat se poate afla in vectorul nesortat pe oricare din pozitiile 1, 2, ..., $k+1$. El se afla asadar in heap-ul $H$; in plus, fiind cel mai mic, stim exact de unde sa-l luam: din varful heap-ului. Deci vom elimina acest element din heap si il vom trece "undeva" separat (vom vedea mai tarziu unde). In loc sa punem in locul lui ultimul element din heap, insa, vom aduce al $k+2$-lea element din vector si il vom lasa sa se cearna. Acum putem fi siguri ca al doilea element ca valoare in vectorul sortat se afla in heap, deoarece el se putea afla in vectorul nesortat undeva pe pozitiile 1, 2, ..., $k+2$, toate aceste elemente figurand in heap (bineinteles ca minimul deja extras se exclude din discutie). Putem sa mergem la sigur, luand al doilea minim direct din varful heap-ului.

Deoarece vectorul este $k-sortat$, rezulta ca elementul care s-ar gasi pe prima pozitie in vectorul sortat se poate afla in vectorul nesortat pe oricare din pozitiile $1$, $2$, ..., $k+1$. El se afla asadar in heap-ul $H$; in plus, fiind cel mai mic, stim exact de unde sa-l luam: din varful heap-ului. Deci vom elimina acest element din heap si il vom trece "undeva" separat (vom vedea mai tarziu unde). In loc sa punem in locul lui ultimul element din heap, insa, vom aduce al $k+2$-lea element din vector si il vom lasa sa se cearna. Acum putem fi siguri ca al doilea element ca valoare in vectorul sortat se afla in heap, deoarece el se putea afla in vectorul nesortat undeva pe pozitiile $1$, $2$, ..., $k+2$, toate aceste elemente figurand in heap (bineinteles ca minimul deja extras se exclude din discutie). Putem sa mergem la sigur, luand al doilea minim direct din varful heap-ului.

Vom proceda la fel pana cand toate elementele vectorului vor fi adaugate in heap. Din acel moment vom continua sa extragem din varful heap-ului, revenind la vechea modalitate de a umple locul ramas gol cu ultimul nod disponibil. Continuam si cu acest procedeu pana cand heap-ul se goleste. In acest moment am obtinut vectorul sortat "undeva" in memorie. De fapt, daca ne gandim putin, vom constata ca, odata ce primele $k+1$ elemente din vector au fost trecute in heap, ordinea lor in vectorul $V$ nu mai conteaza, ele putand servi chiar la stocarea minimelor gasite pe parcurs. Pe masura ce aceste locuri se vor umple, altele noi se vor crea prin trecerea altor elemente in heap. Iata deci cum nici acest algoritm nu necesita memorie suplimentara.