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

==code(c) |
const int MAX_HEAP_SIZE = 16 * 1024;

==code(cpp) |
const int MAX_HEAP_SIZE = 16384;

typedef int Heap[MAX_HEAP_SIZE];
inline int father(int nod) {

h2(#cautarea-maximului). Cautarea maximului

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

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

inline int max(Heap H) {
    return H[1];
}

h2(#creare-heap). 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 fii sai (nodurile 6 si 7):

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 fiii sai (nodurile $6$ si $7$):

!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, anomalia se va pastra. Trebuie deci sa schimbam nodul 3 cu nodul 6:

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$, anomalia 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:

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.

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

==code(cpp) |

void sift(Heap H, int N, int K) {
    int son;
    do {

}
==

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

==code(cpp) |

void percolate(Heap H, int N, int K) {
    int 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 singur 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

p{padding-left: 4em}. _Nivelul frunzelor este organizat_

!heapuri?create6.JPG!

Ultimele doua nivele sunt organizate

p{padding-left: 3em}. _Ultimele doua nivele sunt organizate_

!heapuri?create7.JPG!

Ultimele trei nivele sunt organizate

p{padding-left: 3.5em}. _Ultimele trei nivele sunt organizate_

!heapuri?create8.JPG!

Structura de heap

p{padding-left: 7em}. _Structura de heap_

==code(c) |

==code(cpp) |

void build_heap(Heap H, int N) {

    for (int i = N/2; i > 0; --i) {

    for (int i = N / 2; i > 0; --i) {

        sift(H, N, i);
    }
}
==

S-a apelat caderea incepand de la al $N/2$ - lea nod, deoarece acesta este ultimul nod care mai are fii, restul cu indici mai mari 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>O(\displaystyle {\sum_{k=1}^{[\log_2 N]} k} \times \frac{N}{2^{k+1}}) = O(N)</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.

S-a apelat caderea incepand de la al $N / 2$ - lea nod, deoarece acesta este ultimul nod care mai are fii, restul cu indici mai mari 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>O(\displaystyle {\sum_{k=1}^{[\log_2 N]} k} \times \frac{N}{2^{k+1}}) = O(N)</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(#stergere). Eliminarea unui element, stiind pozitia lui in heap

Sa presupunem ca vrem sa eliminam nodul de valoare 9, aducand in locul lui nodul de valoare X. Insa X poate fi orice numar mai mic sau egal cu 18. Spre exemplu, X poate fi 16, caz in care va trebui urcat deasupra nodului de valoare 10, sau poate fi 1, caz in care va trebui cernut pana la nivelul frunzelor. Deoarece caderea si urcarea se pot face pe cel mult $(log N)$ nivele, rezulta o complexitate a procedeului de $O(log N)$.

==code(c) |

==code(cpp) |

void cut(Heap H, int& N, int K) {
    H[K] = H[N];
    --N;

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

==code(cpp) |

void insert(Heap H, int N, int key) {
    H[++N] = key;
    percolate(H, N, N);

Partea cea mai frumoasa a acestui algoritm 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) |

==code(cpp) |

void heapsort(Heap H, int N) {
    build_heap(H, N);

In continuare vom ilustra cum putem implementa operatiile de extragere a maximului, extragere a minimului, inserare, stergere si cautare folosind un $multiset$. Vom folosi un multiset pentru ca toate copiile unui numar vor fi pastrate daca el va fi inserat de mai multe ori (spre deosebire de set, care il va pastra o singura data). Va recomandam cu caldura sa copiati codul pe calculatorul vostru si sa experimentati cu el pentru a vedea ce afiseaza si a intelege ce se intampla.

==code(c) |

==code(cpp) |

#include <set>
using namespace std;