Ansambluri

Ansambluri

Un arbore cu prioritate este un arbore binar perfect in care fiecare nod are atasata o informatie (numita prioritate) dintr-o multime ordonata astfel incat oricare nod are o prioritate mai mare decat succesorul sau.

O coada cu prioritate este o structura de date in care fiecare element are atasata o prioritate si pentru eliminare este selectat elementul cu cea mai mare prioritate. Structurile stiva si coada sunt cazuri extreme de coada cu prioritate si sunt opuse una celeilalte, deoarece cel mai nou element introdus in stiva capata prioritatea cea mai mare, pe cand cel mai nou element introdus in coada capata prioritatea cea mai mica.

Un ansamblu (heap in limba engleza) este reprezentarea secventiala cu parcurgere in latime a unui arbore cu prioritate.

Exemplul 3.16

Fie arborele binar perfect numerotat in ordine ierarhica totala din figura 3.9 (a). Fiecare nod are asociata o prioritate. Ansamblul este prezentat in figura 3.8(b).

(b)

Fig. 3.9

Structura ansamblu are numeroase aplicatii in domeniul informaticii.