h1. Heap-uri

== include(page="template/implica-te/scrie-articole" user_id="Cyber") ==
 

(Categoria _Structuri de date_, Autor _Catalin Francu_)
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.