Heap

Dicționar

ARBORE

 - Un graf neorientat conex și fără cicluri.

ARBORE BINAR

 - Un arbore care fie este vid, fie constă dintr-un nod rădăcină și doi arbori binari disjuncți numiți subarborele stang, respectiv subarborele drept.

ARBORE BINAR COMPLET

 - Arbore binar care se obține dintr-un arbore binar plin prin eliminarea din dreapta către stânga a unor noduri de pe ultimul nivel.

ARBORE BINAR PLIN

 - Arbore binar care are 2^k-1 vârfuri dispuse pe nivelurile 0,1, ..., k-1, astfel încat pe fiecare nivel i se găsesc 2^i vârfuri.

Noțiuni Introductive

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

Generator Heap

Heap

  1. Creare
  2. Inserare nod
  3. Combinare
  4. Extragere nod

Coadă cu prioritate

Aplicații

Dicționar

ARBORE BINAR STRICT

 - Arbore binar în care orice vârf are gradul zero (este terminal) sau doi (are exact doi fii).

ARBORE BINAR CU RĂDĂCINĂ

 - O mulțime finită de noduri care fie este vidă fie:
-- Există un nod special numit rădăcina arborelui
-- Mulțimea celorlalte noduri este partiționată în n>=0 clase A1, A2, ..., An, fiecare clasa fiind un arbore cu rădăcină. Rădăcina arborelui este unită prin muchii de rădăcinile arborilor A1, A2, ..., An.

COADĂ CU PRIORITATE

 - O structură de date abstractă formată din elemente care au asociată o valoare numită cheie sau prioritate și care suportă urmaoarele operații:
-- Insert(Q,x): inserează elementul x în coadă cu prioritate Q;
-- ExtractMax(Q): extrage elementul de valoare maximă din coada cu prioritate Q.

MAX-HEAP

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

MIN-HEAP

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