![](images/title/maxheapminheap.jpg)
![](images/def.gif)
Un MaxHeap este un arbore
binar complet in care valoarea memorata in orice nod al sau
este mai mare sau egala decat valorile memorate in nodurile fii
ai acestuia. Exemplu
![](images/def.gif)
Un MinHeap este un arbore
binar complet in care valoarea memorata in orice nod al sau
este mai mica sau egala decat valorile memorate in nodurile fii
ai acestuia. Exemplu
REPREZENTARE
Un heap fiind un arbore binar complet, reprezentarea
cea mai adecvata este reprezentarea secventiala. Deci este suficient
sa retinem intr-un vector informatiile asociate nodurilor, relatiile
dintre noduri fiind descrise de formulele:
st(x) = 2*x (daca 2*x<=n) sau NULL (daca 2*x>n);
dr(x) = 2*x+1(daca 2*x+1<=n) sau NULL (daca 2*x+1>n);
tata(x) = [x/2] (daca x>1) sau NULL (daca x=1 este radacina);
unde x este un nod oarecare, iar n este numarul de noduri din
arbore.
Exemplu.
Utilizand reprezentarea secventiala, putem reformula
definitia unui heap astfel:
![](images/def.gif)
Tabloul H[1..n] formeaza un MaxHeap daca H[i]<=H[i/2],
i = 1,n;
![](images/def.gif)
Tabloul H[1..n] formeaza un MinHeap daca H[i]>=H[i/2],
i=1,n;
|