Precizam de asemenea ca heap-ul poate fi organizat pe baza operatorului de $≤$. In acest caz, in varful heap-ului vom avea minimul dintre elementele pastrate in heap. In functie de operatia folosita, putem numi structura de date max-heap sau min-heap. In continuare vom prezenta operatiile intr-un max-heap, adaptarea lor pentru min-heap-uri fiind usoara.

h2. Cautarea maximului

h2. Structura de heap si metode ajutatoare
 
In blocul de cod de mai jos prezentam cum se defineste un heap ca vector si cateva metode ajutatoare:

Practic operatia aceasta nu are de facut decat sa intoarca valoarea primului element din vector:

==code(c) |
const int MAX_HEAP_SIZE = 16 * 1024;
typedef int Heap[MAX_HEAP_SIZE];

void Max(Heap H, int N) {

 
inline int father(int nod) {
  return nod << 1;
}
 
inline int left_son(int nod) {
  return nod >> 1;
}
 
inline int right_son(int nod) {
  return (nod >> 1) + 1;
}
==
 
h2. Cautarea maximului
 
Practic operatia aceasta nu are de facut decat sa intoarca valoarea primului element din vector:
==code(c) |
inline void max(Heap H) {

  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:

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!

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

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)

void sift(Heap H, int N, int K)

{ int Son;
  /* Alege un fiu mai mare ca tatal */

}
==

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:

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)

void percolate(Heap H, int N, int K)

{ int Key;
  Key = H[K];

}
==

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:

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!

void BuildHeap(Heap H, int N)
{ int i;

  for (i=N/2; i; Sift(H, N, i--));

  for (i=N/2; i; sift(H, N, i--));

}
==

*TODO*: Smenul folosit la Dijkstra -- pastrarea unui vector adiacent cu pozitia fiecarui element in heap!

Daca eliminam un element din heap, trebuie numai sa refacem structura de heap. In locul nodului eliminat s-a creat un gol, pe care trebuie sa il umplem cu un alt nod. Care ar putea fi acela? Intrucat trebuie ca toate nivelele sa fie complet ocupate, cu exceptia ultimului, care poate fi gol numai in partea sa dreapta, rezulta ca singurul nod pe care il putem pune in locul celui eliminat este ultimul din heap. Odata ce l-am pus in gaura facuta, trebuie sa ne asiguram ca acest nod "de umplutura" nu strica proprietatea de heap. Deci vom verifica: daca nodul pus in loc este mai mare ca tatal sau, vom apela procedura Percolate. Altfel vom apela procedura Sift, in eventualitatea ca nodul este mai mic decat unul din fiii sai. Iata exemplul de mai jos:

Daca eliminam un element din heap, trebuie numai sa refacem structura de heap. In locul nodului eliminat s-a creat un gol, pe care trebuie sa il umplem cu un alt nod. Care ar putea fi acela? Intrucat trebuie ca toate nivelele sa fie complet ocupate, cu exceptia ultimului, care poate fi gol numai in partea sa dreapta, rezulta ca singurul nod pe care il putem pune in locul celui eliminat este ultimul din heap. Odata ce l-am pus in gaura facuta, trebuie sa ne asiguram ca acest nod "de umplutura" nu strica proprietatea de heap. Deci vom verifica: daca nodul pus in loc este mai mare ca tatal sau, vom apela procedura percolate. Altfel vom apela procedura sift, in eventualitatea ca nodul este mai mic decat unul din fiii sai. Iata exemplul de mai jos:

!heapuri?delete1.JPG!

{ H[K] = H[N--];
  if ((K>1) && (H[K] > H[K>>1]))

    Percolate(H, N, K);
    else Sift(H, N, K)

    percolate(H, N, K);
    else sift(H, N, K)

}
==

void Insert(Heap H, int N, int Key)
{
  H[++N] = Key;

  Percolate(H, N, N);

  percolate(H, N, N);

}
==

{ int i;
  /* Construieste heap-ul */

  for (i=N>>1; i; Sift(H, N, i--));

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

      sift(H, --i, 1);

    }
}
==