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

h2. Definirea notiunii de _HEAP_

In acest articol ne propunem sa prezentam structura de date numita heap-uri. Pentru asta sa pornim de la o problema interesanta mai mult din punct de vedere teoretic:
 
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
 
Vom incepe prin a defini notiunea 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!

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. Aplicatii
 
h2. ============== TODO: Prezentam sau nu problema de mai jos?
PRO:
 
* E interesanta si este o aplicatie a heapurilor
 
CONTRA:

****

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

Sperand ca am reusit sa explicam modul de functionare al unui heap, sa incercam sa rezolvam si problema propusa. 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.

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

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