Heap-uri

Heapuri

h1. Heap-uri

h1. Heapuri

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

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

(Categoria _Structuri de date_, Autor _Catalin Francu_, Versiunea originala preluata din cartea _"Psihologia concursurilor de informatica"_)
(toc){width: 30em}*{text-align:center;} *Continut*

* 'Definirea notiunii de _heap_':heapuri#definirea

* 'Definirea notiunii de _heap_':heapuri#definire

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

* '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
* 'STL':heapuri#stl

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

In acest articol vom prezenta 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 "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:

* va antreneaza mintea

* va veti putea descurca in situatii in care aveti nevoie de o structura de date similara dar nu la fel

* va veti putea descurca in situatii in care aveti nevoie de o structura de date asemanatoare, dar nu la fel

* veti fi utilizatori informati ai bibliotecii STL

* veti intelege cand este bine sa folosoti o structura de date si cand nu
* veti avea avantajul de a sti precis de ce operatiile au anumite complexitati

* veti intelege cand este bine sa folositi o structura de date si cand nu
* veti avea avantajul de a sti precis de ce operatiile de baza au anumite complexitati

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

h2(#definirea). Definirea notiunii de _heap_

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

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:

!heapuri?heap.JPG!

Langa fiecare nod din arbore se afla cate un numar, reprezentand pozitia in vector pe care ar avea-o nodul respectiv. Pentru cazul considerat, vectorul echivalent ar fi  {$H = (12 10 11 10 7 9 3 2 8 1 4 3)$}.

Langa fiecare nod din arbore se afla cate un numar, reprezentand pozitia in vector pe care ar avea-o nodul respectiv. Pentru cazul considerat, vectorul echivalent ar fi {$H = (12 10 11 10 7 9 3 2 8 1 4 3)$}.

Se observa ca nodurile sunt parcurse de la stanga la dreapta si de sus in jos. O proprietate necesara pentru ca un arbore binar sa se poata numi heap este ca toate nivelele sa fie complete, cu exceptia ultimului, care se completeaza incepand de la stanga si continuand pana la un punct. De aici deducem ca inaltimea unui heap cu $N$ noduri este <tex> h=[\log_2 N] </tex> (reamintim ca inaltimea unui arbore este adancimea maxima a unui nod, considerand radacina drept nodul de adancime 0). Reciproc, numarul de noduri ale unui heap de inaltime $h$ este <tex> N\in [2^h, 2^{h+1}-1]</tex>.

Se observa ca nodurile sunt parcurse de la stanga la dreapta si de sus in jos. O proprietate necesara pentru ca un arbore binar sa se poata numi $heap$ este ca toate nivelurile sa fie complete, cu exceptia ultimului, care se completeaza incepand de la stanga si continuand pana la un anume punct. De aici deducem ca inaltimea unui heap cu $N$ noduri este <tex> h=[\log_2 N] </tex> (reamintim ca inaltimea unui arbore este adancimea maxima a unui nod, considerand radacina drept nodul de adancime $0$). Reciproc, numarul de noduri ale unui heap de inaltime $h$ este <tex> N\in [2^h, 2^{h+1}-1]</tex>.

Tot din aceasta organizare mai putem deduce ca tatal unui nod $k > 1$ este nodul $[k/2]$, iar fiii nodului k sunt nodurile $2k$ si $2k+1$. Daca $2k = N$, atunci nodul $2k+1$ nu exista, iar nodul $k$ are un singur fiu; daca $2k > N$, atunci nodul $k$ este frunza si nu are nici un fiu. Exemple: tatal nodului 5 este nodul 2, iar fiii sai sunt nodurile 10 si 11. Tatal nodului 6 este nodul 3, iar unicul sau fiu este nodul 12. Tatal nodului 9 este nodul 4, iar fii nu are, fiind frunza in heap.

Tot din aceasta organizare mai putem deduce ca tatal unui nod $k > 1$ este nodul $[k/2]$, iar fiii nodului $k$ sunt nodurile $2k$ si $2k+1$. Daca $2k = N$, atunci nodul $2k+1$ nu exista, iar nodul $k$ are un singur fiu; daca $2k > N$, atunci nodul $k$ este frunza si nu are niciun fiu. Exemple: tatal nodului $5$ este nodul $2$, iar fiii sai sunt nodurile $10$ si $11$. Tatal nodului $6$ este nodul $3$, iar unicul sau fiu este nodul $12$. Tatal nodului $9$ este nodul $4$, iar fii nu are, fiind frunza in heap.

Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de aflarea a maximului, este aceea ca valoarea oricarui nod este mai mare sau egala cu valoarea oricarui fiu al sau. Dupa cum se vede mai sus, nodul 2 are valoarea 10, iar fiii sai - nodurile 4 si 5 - au valorile 10 si respectiv 7. Intrucat operatorul ≥ este tranzitiv, putem trage concluzia ca un nod este mai mare sau egal decat oricare din nepotii sai si, generalizand, va rezulta ca orice nod este mai mare sau egal decat toate nodurile din subarborele a carui radacina este el.

Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de aflarea a maximului, este aceea ca valoarea oricarui nod este mai mare sau egala cu valoarea oricarui fiu al sau. Dupa cum se vede mai sus, nodul $2$ are valoarea $10$, iar fiii sai - nodurile $4$ si $5$ - au valorile $10$ si respectiv $7$. Intrucat operatorul $≥$ este tranzitiv, putem trage concluzia ca un nod este mai mare sau egal decat oricare din nepotii sai si, generalizand, va rezulta ca orice nod este mai mare sau egal decat toate nodurile din subarborele a carui radacina este.

Aceasta afirmatie nu decide in nici un fel intre valorile a doua noduri dispuse astfel incat nici unul nu este descendent al celuilalt. Cu alte cuvinte, nu inseamna ca orice nod de pe un nivel mic are valoare mai mare decat nodurile mai apropiate de frunze. Este cazul nodului 7, care are valoarea 3 si este mai mic decat nodul 9 de valoare 8, care este totusi asezat ma jos in heap. In orice caz, o prima concluzie care rezulta din aceasta proprietate este ca radacina are cea mai mare valoare din tot heap-ul.

Aceasta afirmatie nu decide in niciun fel intre valorile a doua noduri dispuse astfel incat niciunul nu este descendent al celuilalt. Cu alte cuvinte, nu inseamna ca orice nod de pe un nivel mic are valoare mai mare decat nodurile mai apropiate de frunze. Este cazul nodului $7$, care are valoarea $3$ si este mai mic decat nodul $9$ de valoare $8$, nod asezat totusi mai jos in heap. In orice caz, o prima concluzie care rezulta din aceasta proprietate este ca radacina are cea mai mare valoare din tot heap-ul.

Structura de heap permite efectuarea multor operatii intr-un timp foarte bun:

* Inserarea unui element in $O(log N)$
* Sortarea elementelor din heap in $O(N log N)$

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

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.

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.

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:

==code(c) |
const int MAX_HEAP_SIZE = 16 * 1024;

==code(cpp) |
const int MAX_HEAP_SIZE = 16384;

typedef int Heap[MAX_HEAP_SIZE];
inline int father(int nod) {

}
==

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

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

inline int max(Heap H) {
    return H[1];
}
==

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

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

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 fiii sai (nodurile $6$ si $7$):

!heapuri?create1.JPG!

Ce e de facut ? Desigur, nodul va trebui coborat in arbore, iar in locul lui vom aduce alt nod, mai exact unul dintre fiii sai. Intrebarea este: care din fiii sai ? Daca vom aduce nodul 7 in locul lui, acesta fiind mai mic decat nodul 6, anomalia se va pastra. Trebuie deci sa schimbam nodul 3 cu nodul 6:

Ce e de facut? Desigur, nodul va trebui coborat in arbore, iar in locul lui vom aduce alt nod, mai exact unul dintre fiii sai. Intrebarea este: care din fiii sai? Daca vom aduce nodul $7$ in locul lui, acesta fiind mai mic decat nodul $6$, anomalia se va pastra. Trebuie deci sa schimbam nodul $3$ cu nodul $6$:

!heapuri?create2.JPG!

Problema nu este insa rezolvata, deoarece noul nod 6, proaspat "retrogradat", este inca mai mic decat fiul sau, nodul 12. De data aceasta avem un singur fiu, deci o singura optiune: schimbam nodul 6 cu nodul 12 si obtinem o structura de heap corecta:

Problema nu este insa rezolvata, deoarece noul nod $6$, proaspat "retrogradat", este inca mai mic decat fiul sau, nodul $12$. De data aceasta avem un singur fiu, deci o singura optiune: schimbam nodul $6$ cu nodul $12$ si obtinem o structura de heap corecta:

!heapuri?create3.JPG!

Procedura sift primeste ca parametri un heap $H$ cu $N$ noduri si un nod $K$ si presupune ca ambii subarbori ai nodului $K$ au structura de heap corecta. Misiunea ei este sa "cearna" nodul $K$ pana la locul potrivit, interschimband mereu nodul cu cel mai mare fiu al sau pana cand nodul nu mai are fii (ajunge pe ultimul nivel in arbore) sau pana cand fiii sai au valori mai mici decat el.

Procedura $sift$ primeste ca parametri un heap $H$ cu $N$ noduri si un nod $K$ si presupune ca ambii subarbori ai nodului $K$ au structura de heap corecta. Misiunea ei este sa "cearna" nodul $K$ pana la locul potrivit, interschimband mereu nodul cu cel mai mare fiu al sau pana cand nodul nu mai are fii (ajunge pe ultimul nivel in arbore) sau pana cand fiii sai au valori mai mici decat el.

==code(c) |

==code(cpp) |

void sift(Heap H, int N, int K) {
    int son;
    do {

}
==

Procedura percolate se va ocupa tocmai de fenomenul invers. Sa presupunem ca un heap are o "defectiune" in sensul ca observam un nod care are o valoare mai mare decat tatal sau. Atunci, va trebui sa interschimbam cele doua noduri. Este cazul nodului 10 din figura care urmeaza. Deoarece fiul care trebuie urcat este mai mare ca tatal, care la randul lui (presupunand ca restul heap-ului e corect) este mai mare decat celalalt fiu al sau, rezulta ca dupa interschimbare fiul devenit tata este mai mare decat ambii sai fii. Trebuie totusi sa privim din nou in sus si sa continuam sa urcam nodul in arbore fie pana ajungem la radacina, fie pana ii gasim un tata mai mare ca el. Iata ce se intampla cu nodul 10:

Procedura $percolate$ se va ocupa tocmai de fenomenul invers. Sa presupunem ca un heap are o "defectiune" in sensul ca observam un nod care are o valoare mai mare decat tatal sau. Atunci, va trebui sa interschimbam cele doua noduri. Este cazul nodului $10$ din figura care urmeaza. Deoarece fiul care trebuie urcat este mai mare ca tatal, care la randul lui (presupunand ca restul heap-ului e corect) este mai mare decat celalalt fiu al sau, rezulta ca dupa interschimbare fiul devenit tata este mai mare decat ambii sai fii. Trebuie totusi sa privim din nou in sus si sa continuam sa urcam nodul in arbore fie pana ajungem la radacina, fie pana ii gasim un tata mai mare ca el. Iata ce se intampla cu nodul $10$:

!heapuri?create4.JPG!

==code(c) |

==code(cpp) |

void percolate(Heap H, int N, int K) {
    int key = H[K];

}
==

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 singru 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!

Nivelul frunzelor este organizat

p{padding-left: 4em}. _Nivelul frunzelor este organizat_

!heapuri?create6.JPG!

Ultimele doua nivele sunt organizate

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

!heapuri?create7.JPG!

Ultimele trei nivele sunt organizate

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

!heapuri?create8.JPG!

Structura de heap

p{padding-left: 7em}. _Structura de heap_

==code(c) |

==code(cpp) |

void build_heap(Heap H, int N) {

    for (int i = N/2; i > 0; --i) {

    for (int i = N / 2; i > 0; --i) {

        sift(H, N, i);
    }
}
==

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.

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(#cut). Eliminarea unui element stiind pozitia lui in heap

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)$.
==code(c) |

 
 
 
 
 
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) {
    H[K] = H[N];
    --N;

}
==

h2(#insert). Inserarea unui element

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(c) |
void insert(Heap H, int N, int key) {

==code(cpp) |
void insert(Heap H, int& N, int key) {

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

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

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, la prima vedere destul de mare consumator de memorie, 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(c) |
void heap_sort(Heap H, int N) {

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

    build_heap(H, 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(#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). 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++. 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.
 
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.
 
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). Aplicatii
 
* 'Dijkstra cu heap-uri':http://infoarena.ro/problema/dijkstra
_('codul sursa:':http://infoarena.ro/job_detail/144766?action=view-source)_
* '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) prin micsorarea limitei de memorie.
* Pe astea le-am rezolvat cu set-uri, nu stiu daca merge si cu heap-uri ca au nevoie si de stergere in log(N) -- smenul de la Dijkstra?:
** 'Manager':http://acm.tju.edu.cn/toj/showp1675.html - tju, 1675
** 'Supermarket':http://acm.tju.edu.cn/toj/showp1681.html

h2(#cautare). Cautarea unui element

h2. TODO: Prezentam sau nu problema 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 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.

PRO:

h2(#stl). Alternative STL

* E interesanta si este o aplicatie a heapurilor

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.

CONTRA:

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.

* Este o aplicatie teoretica/fortata
* Mareste prea mult articolul

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.

*Feedback (Stefan):* As sugera transformarea problemei intr-una mai utila si mai putin fortata: Sa se interclaseze in mod eficient $K$ vectori sortati.

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.

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

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

Exemple vreicat mai multe sa dai,pt calumea crede ca heapurile folosesc numai la heap sort si e bine sa schimbam ideea asta. Parerea mea e ca orice concept nou trebuie explicat cu 3 exemple care nu sunt inrudite ca sa il intelegi k lumea.

int main() {
    multiset <int> my_set;
    my_set.insert(1); // Insereaza o valoare.
    my_set.insert(1);

Daca articolul e prea lung ar fimisto sa avem ceva butoane care expandeaza bucati din articol, sau celputin un cuprins la inceput, daca te intereseaza implementarea sau aplicatiile sa poti sari rapid la ce te intereseaza.
 
h2. Problema
 
Sperand ca am reusit sa explicam modul de functionare al unui heap, .
 
Un vector se numeste $k-sortat$ daca orice element al sau se gaseste la o distanta cel mult egala cu $k$ de locul care i s-ar cuveni in vectorul sortat. Iata un exemplu de vector 2-sortat cu 5 elemente:
 
$V=(6 2 7 4 10)$
$V{~sortat~} =(2 4 6 7 10)$
 
Se observa ca elementele 4 si 6 se afla la doua pozitii distanta de locul lor in vectorul sortat, elementele 2 si 7 se afla la o pozitie distanta, iar elementul 10 se afla chiar pe pozitia corecta. Distanta maxima este 2, deci vectorul V este 2-sortat. Desigur, un vector $k-sortat$ este in acelasi timp si un vector $(k+1)-sortat$, si un vector $(k+2)-sortat$ etc., deoarece, daca orice element se afla la o distanta mai mica sau egala cu $k$ de locul potrivit, cu atat mai mult el se va afla la o distanta mai mica sau egala cu $k+1$, $k+2$ etc. In continuare, cand vom spune ca vectorul este $k-sortat$, ne vom referi la cel mai mic $k$ pentru care afirmatia este adevarata. Prin urmare, un vector cu $N$ elemente poate fi $N-1$ sortat in cazul cel mai defavorabil. Mai facem precizarea ca un vector 0-sortat este un vector sortat in intelesul obisnuit al cuvantului, deoarece fiecare element se afla la o distanta egala cu 0 de locul sau.
 
Problema este: dandu-se un vector $k-sortat$ cu $N$ elemente numere intregi, se cere sa-l sortam intr-un timp mai bun decat $O(N*log N)$.
 
Date sunt citite din fisierul $input.txt$ care contine pe prima linie valorile lui $N$ si $K$ ({$2 &le; K < N &le; 10000$}), despartite printr-un spatiu. Pe a doua linie se dau cele $N$ elemente ale vectorului, despartite prin spatii. In fisierul $output.txt$ se vor tipari pe o singura linie elementele vectorului sortat, separate prin spatii.
 
Iata un exemplu:
 
table(example). |_. input.txt |_. output.txt |
| 5
6 2 7 4 10| 2 4 6 7 10 |
 
Ne propunem obtinerea unei complexitati $O(N*logK)$. Evident, putem sorta vectorul fara sa tinem cont de propietatile sale dar am obtine o complexitate $O(N*logN)$. Diferentierea intre aceasta solutie si cea prezentata in continuare este probabil imposibil de facut in regim de concurs. Prezentam totusi solutia $O(N*logK)$ de amorul artei si pentru a ilustra conceptual heapurile :)
 
h2. Rezolvare

    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");
    }

Chiar faptul ca ni se cere o complexitate de ordinul $O(N*log k)$ ne sugereaza construirea unui heap cu $O(k)$ noduri. Sa ne inchipuim ca am construi un heap $H$ format din primele $k+1$ elemente ale vectorului $V$.  Diferenta fata de ce am spus pana acum este ca orice nod va trebui sa fie mai mic decat fiii sai. Acest heap va servi deci la extragerea minimului.

    // 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 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(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;
}
==

Deoarece vectorul este $k-sortat$, rezulta ca elementul care s-ar gasi pe prima pozitie in vectorul sortat se poate afla in vectorul nesortat pe oricare din pozitiile $1$, $2$, ..., $k+1$. El se afla asadar in heap-ul $H$; in plus, fiind cel mai mic, stim exact de unde sa-l luam: din varful heap-ului. Deci vom elimina acest element din heap si il vom trece "undeva" separat (vom vedea mai tarziu unde). In loc sa punem in locul lui ultimul element din heap, insa, vom aduce al $k+2$-lea element din vector si il vom lasa sa se cearna. Acum putem fi siguri ca al doilea element ca valoare in vectorul sortat se afla in heap, deoarece el se putea afla in vectorul nesortat undeva pe pozitiile $1$, $2$, ..., $k+2$, toate aceste elemente figurand in heap (bineinteles ca minimul deja extras se exclude din discutie). Putem sa mergem la sigur, luand al doilea minim direct din varful heap-ului.

h2(#aplicatii). Aplicatii

Vom proceda la fel pana cand toate elementele vectorului vor fi adaugate in heap. Din acel moment vom continua sa extragem din varful heap-ului, revenind la vechea modalitate de a umple locul ramas gol cu ultimul nod disponibil. Continuam si cu acest procedeu pana cand heap-ul se goleste. In acest moment am obtinut vectorul sortat "undeva" in memorie. De fapt, daca ne gandim putin, vom constata ca, odata ce primele $k+1$ elemente din vector au fost trecute in heap, ordinea lor in vectorul $V$ nu mai conteaza, ele putand servi chiar la stocarea minimelor gasite pe parcurs. Pe masura ce aceste locuri se vor umple, altele noi se vor crea prin trecerea altor elemente in heap. Iata deci cum nici acest algoritm nu necesita memorie suplimentara.

* 'Dijkstra cu heap-uri':http://infoarena.ro/problema/dijkstra
* '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 - 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