Heap

MaxHeap și MinHeap

Definiție

 Un MaxHeap este un arbore binar complet în care valoarea memorată în orice nod al său este mai mare sau egală decât valorile memorate în nodurile fii ai acestuia.
Un MinHeap este un arbore binar complet în care valoarea memorată în orice nod al său este mai mică sau egală decât valorile memorate în nodurile fii ai acestuia.

REPREZENTARE

 Un heap fiind un arbore binar complet, reprezentarea cea mai adecvată este reprezentarea secvențială. Deci este suficient să reținem într-un vector informațiile asociate nodurilor, relațiile dintre noduri fiind descrise de formulele:
- st(x)=2*x (dacă 2*x<=n) sau NULL (dacă 2*x>n);
- dr(x)=2*x+1(dacă 2*x+1<=n) sau NULL (dacă 2*x+1>n);
- tata(x)=[x/2] (dacă x>1) sau NULL (dacă x=1 este rădăcină);
- unde x este un nod oarecare, iar n este numărul de noduri din arbore.

Noțiuni Introductive

  1. Arbori
  2. Arbori binari
  3. Heap-uri

Generator Heap

Heap

  1. Creare
  2. Inșerare nod
  3. Combinare
  4. Extragere nod

Coadă cu prioritate

Aplicații

Dicționar


Utilizând reprezentarea secvențială, putem reformula definiția unui heap astfel:

Definiție

 Tabloul H[1..n] formează un MaxHeap dacă H[i]<=H[i/2], i=1,n;
Tabloul H[1..n] formează un MinHeap dacă H[i]>=H[i/2], i=1,n;