h1. Heap-uri

*Feedback(Silviu)*: Trebuie sa mentionam (undeva pe la sfarsit sa nu le taiem interesul :P) ca heap-urile vin implementate de-a gata in STL (priority_queue<>). Un exemplu de folosire al lor ar fi belea, eventual chiar rezolvarea problemei "teoretice" propuse. Ma ofer eu sa scriu codul. Apropo, cred ca trebuie inclusa si codul din carte.
*Feedback(Silviu)*: Ne trebuie exemple de probleme care se fac cu heap-uri. Erau cateva pe timus, mai e si aia smechera a lu Berinde de la loturi (sea parca se chema).
 

== include(page="template/implica-te/scrie-articole" user_id="Cyber") ==
(Categoria _Structuri de date_, Autor _Catalin Francu_)

*Feedback(Silviu)*: Trebuie sa mentionam (undeva pe la sfarsit sa nu le taiem interesul :P) ca heap-urile vin implementate de-a gata in STL (priority_queue<>). Un exemplu de folosire al lor ar fi belea, eventual chiar rezolvarea problemei "teoretice" propuse. Ma ofer eu sa scriu codul. Apropo, cred ca trebuie inclusa si codul din carte.
*Feedback(Silviu)*: Ne trebuie exemple de probleme care se fac cu heap-uri. Erau cateva pe timus, mai e si aia smechera a lu Berinde de la loturi (sea parca se chema).
 

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

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
 
TODO: HEAP-uri implementate de mana VS priority_queue<> VS set<>
 

h2. 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
* Sea (Berinde), Baraj ONI 2004 TODO: Pus pe infoareana, fortat o structura de date care intretine dinamic evenimentele (de exemplu heap).
* Pe astea le-am rezolvat cu set-uri, nu stiu daca merge si cu heap-uri:
** 'Manager':http://acm.tju.edu.cn/toj/showp1675.html - tju, 1675
** 'Supermarket':http://acm.tju.edu.cn/toj/showp1681.html
 

h2. TODO: Prezentam sau nu problema de mai jos?
PRO: