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

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:

Tabloul H[1..n] formeaza un MaxHeap daca H[i]<=H[i/2], i = 1,n;

Tabloul H[1..n] formeaza un MinHeap daca H[i]>=H[i/2], i=1,n;