* 'Inserarea unui element':heapuri#insert
* 'Sortarea unui vector (heapsort)':heapuri#heap_sort
* 'Cautarea unui element':heapuri#find

* 'STL':heapuri#stl

* 'Alternative STL':heapuri#stl

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:

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). STL

h2(#stl). Alternative STL

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

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.

Desi nu sunt greu de implementat, avem vesti bune pentru programatorii in C++. In STL, cozile de prioritate (adica max-heap-urile) sunt deja implementate. Totusi, mentionam ca priority_queue nu este in standard-ul STL, aceasta inseamnand ca nu vor fi gasite neaparat in toate implementarile STL. Desi asta reprezinta un risc (e posibil sa nu gasitit priority_queue pe calculatoarele de la concurs) acesta esta minin.

Totusi, in unele aplicatii avem nevoie de o structura de date care suporta operatiile amintite toate in timp $O(logN)$ (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.

O alternativa la priority_queue-uri sunt set-urile si multiset-urile din STL. Acestea au doua avantaje: sunt in standard STL (deci nu riscati nimic) si pot efectua si cautari in O(logN) fiindca sunt implementate ca 'arbori binari echilibrati':arbori-binari-echilibrati. Totusi avantajele vin cu un cost: set-urile si multiset-urile pot fi mai incete decat cozile de prioritate.
 
Daca nu sunteti familiari cu aceste structuri de date, va recomandam sa cititi paginile lor de documentatie: 'priority_queue<>':http://www.sgi.com/tech/stl/priority_queue.html, 'set<>':http://www.sgi.com/tech/stl/set.html si 'multiset':http://www.sgi.com/tech/stl/multiset.html. Daca nu intelegeti chiar tot de la inceput (pentru ca nu stiti clase si template-uri in C++), uitati-va pe exemple si pe lista de functii membre si invatati cum se folosesc.

Daca nu sunteti familiari cu aceste structuri de date, va recomandam sa cititi paginile lor de documentatie: 'priority_queue':http://www.sgi.com/tech/stl/priority_queue.html, 'set':http://www.sgi.com/tech/stl/set.html si 'multiset':http://www.sgi.com/tech/stl/multiset.html. Daca nu intelegeti totul de la inceput (pentru ca nu stiti clase si template-uri in C++), uitati-va pe exemple si pe lista de functii membre si invatati cum se folosesc.

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).

==code(c) |
#include <set>
using namespace std;
 
int main() {
    multiset<int> my_set;
    my_set.insert(1); // Insereaza o valoare.
    my_set.insert(1);
 
    if (my_set.find(1) != my_set.end()) { // Cauta o valoare.
        printf("Am gasit 1 in set!\n");
    } else {
        printf("1 nu se afla set!\n");
    }
 
    // Sterge o valoare din set. Daca acesta se afla de mai multe ori in set
    // este stearsa numai o copie.
    my_set.erase(my_set.find(1));
    printf("Exista %d elemente in set\n", my_set.size());
 
    my_set.insert(1);
    my_set.insert(1);
 
    // Sterge o valoare din set. Daca acesta se afla de mai multe ori in set
    // sunt sterse toate copiile.
    my_set.erase(1);
    printf("Exista %d elemente in set\n", my_set.size());
 
    my_set.insert(1);
    my_set.insert(-3);
    my_set.insert(7);
 
    // Valoarea minima.
    multiset<int>::iterator it = my_set.begin();
    printf("Valoarea cea mai mica din set este %d\n", *it);
 
    // Valoarea maxima.
    it = my_set.end();
    --it;
    printf("Valoarea cea mai mare din set este %d\n", *it);
    return 0;
}
==
 

h2(#aplicatii). Aplicatii
* 'Dijkstra cu heap-uri':http://infoarena.ro/problema/dijkstra