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

Sa pornim de la o problema interesanta mai mult din punct de vedere teoretic:

h2. Introducere

h2. Enunt

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

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

h2. Date de intrare

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.

Fisierul $input.txt$ contine pe prima linie valorile lui $N$ si $K$ , despartite printr-un spatiu. Pe a doua linie se dau cele $N$ elemente ale vectorului, despartite prin spatii.
 
h2. Date de iesire
 
In fisierul $output.txt$ se vor tipari pe o singura linie elementele vectorului sortat, separate prin spatii.
 
Exemplu:

Iata un exemplu:

table(example). |_. input.txt |_. output.txt |
| 5
6 2 7 4 10| 2 4 6 7 10 |

h2. Restrictii si precizari
 
* $2 &le; K < N$
* $N &le; 10000$
* Timp de implementare: 45 minute.
* Timp de rulare: 5 secunde. ????
* Complexitate ceruta: $O(N*log K)$.

Ne propunem obtinerea unei complexitati $O(N * log K)$. Evident, putem sorta vectorul fara sa tinem cont de propietatile sale dar am obtine o complexitate $O(N * log N)$. Diferentierea intre aceasta solutie si cea prezentata in continuare este probabil imposibil de facut in regim de concurs. Prezentam totusi solutia, pentru a ilustra un exemplu de folosire a heapurilor.

h2. Rezolvare