{
  return Hi1s;
}

==

==
 
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.
 
==code(c) |
void Insert(Heap H, int N, int Key)
{
  H[++N] = Key;
  Percolate(H, N, N);
}
==
 
h2. Sortarea unui vector (heapsort)
 
Acum, ca am stabilit toate aceste lucruri, ideea algoritmului de sortare vine de la sine. Incepem prin a construi un heap. Apoi extragem maximul (adica varful heap-ului) si refacem heap-ul. Cele doua operatii luate la un loc dureaza $O(1)+O(log N) = O(log N)$. Apoi extragem din nou maximul, (care va fi al doilea element ca marime din vector) si refacem din nou heap-ul. Din nou, complexitatea operatiei compuse este $O(log N)$. Daca facem acest lucru de $N$ ori, vom obtine vectorul sortat intr-o complexitate de $O(N log N)$.
 
Partea cea mai frumoasa a acestui algoritm, la prima vedere destul de mare consumator de memorie, este ca el nu foloseste deloc memorie suplimentara. Iata explicatia: cand heap-ul are $N$ elemente, vom extrage maximul si il vom tine minte undeva in memorie. Pe de alta parte, in locul maximului (adica in radacina arborelui) trebuie adus ultimul element al vectorului, adica $H[N]$. Dupa aceasta operatie, heap-ul va avea $N-1$ noduri, al $N$-lea ramanand liber. Ce alt loc mai inspirat decat acest al $N$-lea nod ne-am putea dori pentru a stoca maximul ? Practic, am interschimbat radacina, adica pe $H[1]$ cu $H[N]$. Acelasi lucru se face la fiecare pas, tinand cont de micsorarea permanenta a heap-ului.
 
==code(c) |
void HeapSort(Heap H, int N)
{ int i;
 
  /* Construieste heap-ul */
  for (i=N>>1; i; Sift(H, N, i--));
  /* Sorteaza vectorul */
  for (i=N; i>=2;)
    { G[1]=(G[1]^G[i])^(G[i]=G[1]);
      Sift(H, --i, 1);
    }
}
==
 
h2. Cautarea unui element
 
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.