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:

!heapuri?ksortat.JPG!

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

* $N ≤ 10000$
* Timp de implementare: 45 minute.
* Timp de rulare: 5 secunde. ????

* Complexitate ceruta: $O(N * log K)$.

* Complexitate ceruta: $O(N*log K)$.

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:

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:

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

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

!heapuri?vector.JPG!
 
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 de ducem ca inaltimea unui heap cu $N$ noduri este
 
!heapuri?inaltime.JPG!
 
(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:
 
!heapuri?nr.JPG!

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 de ducem 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^n, 2^{n+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.

Dar cea mai importanta proprietate a heap-ului, cea care il face util in operatiile de cautare, 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 cautare, 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.

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.

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

typedef int Heapi10001s;

typedef int Heap[10001];

void Max(Heap H, int N)
{
  return H[1];
}
==

h2. 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 nodul 6:
 
!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, inegalitatea 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:
 
!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.
 
==code(c) |
void Sift(Heap H, int N, int K)
{ int Son;
 
  /* Alege un fiu mai mare ca tatal */
  if (K<<1<=N)
    {
      Son=K<<1;
      if (K<<1<N && H[(K<<1)+1 ] > H[ (K<<1) ])
        Son++;
      if (H[Son]<=H[K]) Son=0;
    }
  else Son=0;
  while (Son)
    { /* Schimba H[K] cu H[Son] */
      H[K]=(H[K]^H[Son]) ^ (H[Son]=H[K]);
      K=Son;
      /* Alege un alt fiu */
      if (K<<1<=N)
        { Son=K<<1;
          if (K<<1<N && H[ (K<<1)+1 ] > H[ (K<<1) ])
            Son++;
          if (H[Son]<=H[K]) Son=0;
        }
        else Son=0;
    }
}
==
 
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) |
void Percolate(Heap H, int N, int K)
{ int Key;
 
  Key = H[K];
  while ((K>1) && (Key > H[ K>>1 ]))
    { H[K]=H[ K>>1 ];
      K>>=1;
    }
  H[K] = Key;
}
==
 
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:
 
!heapuri?create5.JPG!
Nivelul frunzelor este organizat
 
!heapuri?create6.JPG!
Ultimele doua nivele sunt organizate
 
!heapuri?create7.JPG!
Ultimele trei nivele sunt organizate
 
!heapuri?create8.JPG!
Structura de heap
 
==code(c) |
void BuildHeap(Heap H, int N)
{ int i;
 
  for (i=N/2; 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> \sum_{k=1}^{[\log_2 N]} k * \frac{N}{2^{k+1}} </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. 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.