Heap-uri

Heapuri

h1. Heap-uri

h1. Heapuri

== include(page="template/implica-te/scrie-articole-2" user_id1="Cyber" user_id2="silviug") ==

Mentionam ca operatia de cautare a unui element are complexitatea $O(N)$ dar, de obicei, heap-ul nu este folosit cand acest tip de operatii este frecvent.

Desigur, toate aceste operatii se fac mentinand permanent structura de heap a arborelui, adica respectand modul de repartizare a nodurilor pe nivele si plasarea mai sus a elementelor de valoare mai mare. Este de la sine inteles ca datele nu se vor reprezenta in memorie in forma arborescenta, ci in cea vectoriala.

Desigur, toate aceste operatii se fac mentinand permanent structura de heap a arborelui, adica respectand modul de repartizare a nodurilor pe niveluri si plasarea mai sus a elementelor de valoare mai mare. Este de la sine inteles ca datele nu se vor reprezenta in memorie in forma arborescenta, ci in cea vectoriala.

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

}
==

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 singur 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 singur 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 niveluri 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!

!heapuri?create6.JPG!

p{padding-left: 3em}. _Ultimele doua nivele sunt organizate_

p{padding-left: 3em}. _Ultimele doua niveluri sunt organizate_

!heapuri?create7.JPG!

p{padding-left: 3.5em}. _Ultimele trei nivele sunt organizate_

p{padding-left: 3.5em}. _Ultimele trei niveluri sunt organizate_

!heapuri?create8.JPG!

}
==

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)$ niveluri, 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 niveluri, si asa mai departe, pana ajungem la radacina care se afla singura pe nivelul ei si va putea cadea maxim $h$ niveluri (reamintim ca <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.

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

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 nivelurile 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. O data 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:

!heapuri?delete1.JPG!

Sa presupunem ca vrem sa eliminam nodul de valoare 9, aducand in locul lui nodul de valoare X. Insa X poate fi orice numar mai mic sau egal cu 18. Spre exemplu, X poate fi 16, caz in care va trebui urcat deasupra nodului de valoare 10, sau poate fi 1, caz in care va trebui cernut pana la nivelul frunzelor. Deoarece caderea si urcarea se pot face pe cel mult $(log N)$ nivele, rezulta o complexitate a procedeului de $O(log N)$.

 
 
 
 
 
 
Sa presupunem ca vrem sa eliminam nodul de valoare $9$, aducand in locul lui nodul de valoare $X$. Insa $X$ poate fi orice numar mai mic sau egal cu $18$. Spre exemplu, $X$ poate fi $16$, caz in care va trebui urcat deasupra nodului de valoare $10$, sau poate fi $1$, caz in care va trebui cernut pana la nivelul frunzelor. Deoarece caderea si urcarea se pot face pe cel mult $[log N]$ niveluri, rezulta o complexitate a procedeului de $O(log N)$.

==code(cpp) |
void cut(Heap H, int& N, int K) {

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

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]$ niveluri, de unde complexitatea logaritmica.

==code(cpp) |

void insert(Heap H, int N, int key) {

void insert(Heap H, int& N, int key) {

    H[++N] = key;
    percolate(H, N, N);
}

h2(#heapsort). 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)$.

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

Partea cea mai frumoasa a acestui algoritm este ca el nu foloseste deloc memorie suplimentara. Iata explicatia: cand heap-ul are $N$ elemente, vom extrage maximul si il vom tine minte undeva in memorie. Pe de alta parte, in locul maximului (adica in radacina arborelui) trebuie adus ultimul element al vectorului, adica $H[N]$. Dupa aceasta operatie, heap-ul va avea $N-1$ noduri, al $N$-lea ramanand liber. Ce alt loc mai inspirat decat acest al $N$-lea nod ne-am putea dori pentru a stoca maximul? Practic, am interschimbat radacina, adica pe $H[1]$ cu $H[N]$. Acelasi lucru se face la fiecare pas, tinand cont de micsorarea permanenta a heap-ului.

Partea cea mai frumoasa a acestui algoritm este ca el nu foloseste deloc memorie suplimentara. Iata explicatia: cand heap-ul are $N$ elemente, vom extrage maximul si il vom tine minte undeva in memorie. Pe de alta parte, in locul maximului (adica in radacina arborelui) trebuie adus ultimul element al vectorului, adica $H[N]$. Dupa aceasta operatie, heap-ul va avea $N - 1$ noduri, al $N$-lea ramanand liber. Ce alt loc mai inspirat decat acest al $N$-lea nod ne-am putea dori pentru a stoca maximul? Practic, am interschimbat radacina, adica pe $H[1]$ cu $H[N]$. Acelasi lucru se face la fiecare pas, tinand cont de micsorarea permanenta a heap-ului.

==code(cpp) |
void heapsort(Heap H, int N) {

    // Sorteaza vectorul.
    for (int i = N; i >= 2; --i) {
        swap(H[1], H[i]);

        sift(H, i, 1);

        sift(H, i - 1, 1);

    }
}
==
h2(#cautare). 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.

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 ei 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++: 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 operatiile 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.

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 mentinute ca arbori binari echilibrati. Singurele dezavantaje sunt ca de obicei merg mai incet decat cozile de prioritate si folosesc mai multa memorie.

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.

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 $multiset$. 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). Va recomandam cu caldura sa copiati codul pe calculatorul vostru si sa experimentati cu el pentru a vedea ce afiseaza si a intelege ce se intampla.

In continuare vom ilustra cum putem implementa operatiile de extragere a maximului, extragere a minimului, inserare, stergere si cautare folosind un $multiset$. 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). Va recomandam cu caldura sa copiati codul pe calculatorul vostru si sa experimentati cu el pentru a vedea ce afiseaza si a intelege ce se intampla.

==code(cpp) |
#include <set>
using namespace std;
int main() {

    multiset<int> my_set;

    multiset <int> my_set;

    my_set.insert(1); // Insereaza o valoare.
    my_set.insert(1);

        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.

    // Sterge o valoare din set. Daca aceasta 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.

    // Sterge o valoare din set. Daca aceasta 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(7);
    // Valoarea minima.

    multiset<int>::iterator it = my_set.begin();

    multiset <int> :: iterator it = my_set.begin();

    printf("Valoarea cea mai mica din set este %d\n", *it);
    // Valoarea maxima.

* 'Magnetic storms':http://acm.timus.ru/problem.aspx?space=1&num=1126
* 'Manager':http://acm.tju.edu.cn/toj/showp1675.html
* 'Supermarket':http://acm.tju.edu.cn/toj/showp1681.html

* Sea, Radu Berinde - Baraj ONI 2004
* 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.

* Sea - Baraj ONI 2004 (Autor: Radu Berinde)
* Interclasati $K$ vectori sortati. (Sugestie: 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 cand dispuneti de memorie mult mai putina ca $O(N)$. ({$K$} este mult mai mic decat $N$)

3528