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.

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.

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. Singurul dejavantaj este 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.

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

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(c) |
#include <set>

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

* Sea, Radu Berinde - Baraj ONI 2004
* 'Manager':http://acm.tju.edu.cn/toj/showp1675.html - tju, 1675
* 'Supermarket':http://acm.tju.edu.cn/toj/showp1681.html
* 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 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.

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