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

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

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

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_

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:

Precizam de asemenea ca heap-ul poate fi organizat pe baza operatorului de $≤$. In acest caz, in varful heap-ului vom avea minimul dintre elementele pastrate in heap. In functie de operatia folosita, 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 de heap si metode ajutatoare

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

In blocul de cod de mai jos prezentam cum se defineste un heap ca vector si cateva metode ajutatoare:

}
==

h2. 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. 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 nodul 6:

S-a apelat caderea incepand de la al $N/2$ - lea nod, deoarece s-a aratat ca acesta este ultimul nod care mai are fii, restul 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. 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. 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. 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. 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

h2(#stl). STL

*TODO*: HEAP-uri implementate de mana VS priority_queue<> VS set<>

In continuare vom ilustra cum putem implementa operatiile de extragere a maximului, extragere a minimului, inserare, stergere si cautare folosind un multi_set. Vom folosi un multiset pentru ca toate copiile unui numar vor fi pastrate daca el va fi inserat de mai multe ori (spre deosebire de set, care il va pastra o singura data).

h2. Aplicatii

h2(#aplicatii). Aplicatii

* Dijkstra cu heap-uri TODO: pus link la articolul cu Dijkstra cand e gata :P
* 'Magnetic storms':http://acm.timus.ru/problem.aspx?space=1&num=1126 - timus, 1126