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

(toc){width: 20em}*{text-align:center;} *Continut*
* 'Definirea notiunii de _heap_':heapuri#definire

(toc){width: 30em}*{text-align:center;} *Continut*
* 'Definirea notiunii de _heap_':heapuri#definirea

* 'Structura de heap si metode ajutatoare':heapuri#structura

* 'Cautarea maximului':heapuri#cautarea-maximului
* 'Crearea unei structuri de heap dintr-un vector oarecare':heapuri#creare-heap
* 'Eliminarea unui element, stiind pozitia lui in heap':heapuri#stergere
* 'Inserarea unui element':heapuri#inserare
* 'Sortarea unui vector (heapsort)':heapuri#heapsort
* 'Cautarea unui element':heapuri#cautare

* 'Cautarea maximului':heapuri#cautarea_maximului
* 'Crearea unei structuri de heap dintr-un vector oarecare':heapuri#build_heap
* 'Eliminarea unui element stiind pozitia lui in heap':heapuri#cut
* 'Inserarea unui element':heapuri#insert
* 'Sortarea unui vector (heapsort)':heapuri#heap_sort
* 'Cautarea unui element':heapuri#find

* '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:

Acum ca avem o motivatie, sa studiem impreuna heap-urile.

h2(#definire). Definirea notiunii de _heap_

h2(#definirea). 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:

}
==

h2(#cautarea-maximului). Cautarea maximului

h2(#cautarea_maximului). Cautarea maximului

Practic operatia aceasta nu are de facut decat sa intoarca valoarea primului element din vector:
==code(c) |

}
==

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

h2(#build_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):

}
==

S-a apelat caderea incepand de la al $N/2$ - lea nod, deoarece acesta este ultimul nod care mai are fii, restul cu indici mai mari fiind frunze. Sa calculam acum complexitatea acestui algoritm. Un calcul sumar ar putea spune: exista $N$ noduri, fiecare din ele se "cerne" pe $O(log N)$ nivele, deci timpul de constructie a heap-ului este $O(N log N)$. Totusi nu este asa. Presupunem ca ultimul nivel al heap-ului este plin. In acest caz, jumatate din noduri vor fi frunze si nu se vor cerne deloc. Un sfert din noduri se vor afla deasupra lor si se vor cerne cel mult un nivel. O optime din noduri se vor putea cerne cel mult doua nivele, si asa mai departe, pana ajungem la radacina care se afla singura pe nivelul ei si va putea cadea maxim h nivele (reamintim <tex> h=[\log_2 N] </tex>). Rezulta ca timpul total de calcul este dat de formula <tex>O(\displaystyle {\sum_{k=1}^{[\log_2 N]} k} \times \frac{N}{2^{k+1}}) = O(N)</tex>. Demonstrarea egalitatii se poate face facand substitutia $N = 2^h^$ si continuand calculele. Se va obtine tocmai complexitatea $O(2^h^)$. Lasam aceasta verificare ca tema cititorului.

S-a apelat caderea incepand de la al $N/2$ - lea nod, deoarece acesta este ultimul nod care mai are fii, restul cu indici mai mari fiind frunze. Sa calculam acum complexitatea acestui algoritm. Un calcul sumar ar putea spune: exista $N$ noduri, fiecare din ele se "cerne" pe $O(log N)$ nivele, deci timpul de constructie a heap-ului este $O(N log N)$. Totusi nu este asa. Presupunem ca ultimul nivel al heap-ului este plin. In acest caz, jumatate din noduri vor fi frunze si nu se vor cerne deloc. Un sfert din noduri se vor afla deasupra lor si se vor cerne cel mult un nivel. O optime din noduri se vor putea cerne cel mult doua nivele, si asa mai departe, pana ajungem la radacina care se afla singura pe nivelul ei si va putea cadea maxim h nivele (reamintim <tex> h=[\log_2 N] </tex>). Rezulta ca timpul total de calcul este dat de formula <tex>O({\sum_{k=1}^{[\log_2 N]} k} \times \frac{N}{2^{k+1}}) = O(N)</tex>. Demonstrarea egalitatii se poate face facand substitutia $N = 2^h^$ si continuand calculele. Se va obtine tocmai complexitatea $O(2^h^)$. Lasam aceasta verificare ca tema cititorului.

h2(#stergere). Eliminarea unui element, stiind pozitia lui in heap

h2(#cut). Eliminarea unui element stiind pozitia lui in heap

Daca eliminam un element din heap, trebuie numai sa refacem structura de heap. In locul nodului eliminat s-a creat un gol, pe care trebuie sa il umplem cu un alt nod. Care ar putea fi acela? Intrucat trebuie ca toate nivelele sa fie complet ocupate, cu exceptia ultimului, care poate fi gol numai in partea sa dreapta, rezulta ca singurul nod pe care il putem pune in locul celui eliminat este ultimul din heap. Odata ce l-am pus in gaura facuta, trebuie sa ne asiguram ca acest nod "de umplutura" nu strica proprietatea de heap. Deci vom verifica: daca nodul pus in loc este mai mare ca tatal sau, vom apela procedura percolate. Altfel vom apela procedura sift, in eventualitatea ca nodul este mai mic decat unul din fiii sai. Iata exemplul de mai jos:

}
==

h2(#inserare). Inserarea unui element

h2(#insert). Inserarea unui element

Daca vrem sa inseram un nou element in heap, lucrurile sunt mult mai simple. Nu avem decat sa-l asezam pe a $N+1$-a pozitie in vector si apoi sa-l "promovam" pana la locul potrivit. Din nou, urcarea se poate face pe maxim $(log N)$ nivele, de unde complexitatea logaritmica.

}
==

h2(#heapsort). Sortarea unui vector (heapsort)

h2(#heap_sort). Sortarea unui vector (heapsort)

Acum, ca am stabilit toate aceste lucruri, ideea algoritmului de sortare vine de la sine. Incepem prin a construi un heap. Apoi extragem maximul (adica varful heap-ului) si refacem heap-ul. Cele doua operatii luate la un loc dureaza $O(1)+O(log N) = O(log N)$. Apoi extragem din nou maximul, (care va fi al doilea element ca marime din vector) si refacem din nou heap-ul. Din nou, complexitatea operatiei compuse este $O(log N)$. Daca facem acest lucru de $N$ ori, vom obtine vectorul sortat intr-o complexitate de $O(N log N)$.

}
==

h2(#cautare). Cautarea unui element

h2(#find). Cautarea unui element

Aceasta operatie este singura care nu poate fi optimizata (in sensul reducerii complexitatii sub $O(N)$). Aceasta deoarece putem fi siguri ca un nod mai mic este descendentul unuia mai mare, dar nu putem sti daca se afla in subarborele stang sau drept; din aceasta cauza, nu putem face o cautare binara. Totusi, o oarecare imbunatatire se poate aduce fata de cautarea secventiala. Daca radacina unui subarbore este mai mica decat valoarea cautata de noi, cu atat mai mult putem fi convinsi ca descendentii radacinii vor fi si mai mici, deci putem sa renuntam la a cauta acea valoare in tot subarborele. In felul acesta, se poate intampla ca bucati mari din heap sa nu mai fie explorate inutil. Pe cazul cel mai defavorabil, insa, parcurgerea intregului heap este necesara. Lasam scrierea unei proceduri de cautare pe seama cititorului.
h2(#stl). Alternative STL

Desi nu sunt greu de implementat, avem vesti bune pentru programatorii in C++: heap-urile sunt deja implementate in STL. Containerul se numeste 'priority_queue':http://www.sgi.com/tech/stl/priority_queue.html si implementeaza toate operatiile prezentate mai putin operatia de cautare a unei valori si de stergere a unui nod. Aceste doua operatii sunt destul de atipice pentru o coada de prioritati si in general nu sunt asociate cu aceasta structura de date in cartile de algoritmi.

Desi nu sunt greu de implementat, avem vesti bune pentru programatorii in C++: heapurile sunt deja implementate in STL. Containerul se numeste 'priority_queue':http://www.sgi.com/tech/stl/priority_queue.html si implementeaza toate operatiile prezentate mai putin operatia de cautare a unei valori si de stergere a unui nod. Aceste doua operatii sunt destul de atipice pentru o coada de prioritati si in general nu sunt asociate cu aceasta structura de date in cartile de algoritmi.

Totusi, in unele aplicatii avem nevoie de o structura de date care suporta toate operatiile amintite in timp cel mult logaritmic (inclusiv stergerea si cautarea unei valori). Aceasta structura exista deja in STL: $set$-urile. Acestea sunt de fapt multimi intretinute ca 'arbori binari echilibrati':arbori-binari-echilibrati. Singurul dejavantaj este ca de obicei merg mai incet decat cozile de prioritate si folosesc mai multa memorie.

* Interclasti $K$ vectori sortati (Hint: complexitatea dorita este $O(N * log K)$, unde $N$ este lungimea sirului rezultat prin interclasare).
* Determinati cele mai mici $K$ elemente dintr-un sir cu $N$ elemente ({$K$} este mult mai mic decat $N$).

*Feedback (Cosmin):* Merge problema, zic ca trebuie bagata, eventual daca e prea artificiala o punem ultima. E misto problema lui Stefan, alta problema ar fi sa se determine cele mai mici k elemente dintr-un sir de lungime n daca ai memorie << O(n). In cod ar trebui schimbate siftarile cu 1 cu inmultiri si impartiri cu 2, si pare mai putin exoteric codul. Alta chestie, am putea numi articolul cozi de prioritati si sa mentionam heap-uri interclasabile, sau cozi de prioritati cand costurile sunt mici. Am putea sa bagam observatiile cu celelalte cozi de prioritati ca si in Cormen intr-o sectiune la sfarsitul articolului cu extinderi.

*Feedback (Cosmin):* Merge problema, zic ca trebuie bagata, eventual daca e prea artificiala o punem ultima. E misto problema lui Stefan, alta problema ar fi sa se determine cele mai mici k elemente dintr-un sir de lungime n daca ai memorie << O(n). In cod ar trebui schimbate siftarile cu 1 cu inmultiri si impartiri cu 2, si pare mai putin exoteric codul. Alta chestie, am putea numi articolul cozi de prioritati si sa mentionam heapuri interclasabile, sau cozi de prioritati cand costurile sunt mici. Am putea sa bagam observatiile cu celelalte cozi de prioritati ca si in Cormen intr-o sectiune la sfarsitul articolului cu extinderi.