O coada cu prioritate este o structura de date abstracta formata din elemente care au asociata o valoare numita cheie sau prioritate si care suporta urmatoarele operatii:

- Insert(Q,x): insereaza elementul x in coada cu prioritate Q;
- ExtractMax(Q): extrage elementul de valoare maxima din coada cu prioritate Q.

Observatie!
In mod analog se poate defini o coada cu min-prioritate, pentru care intereseaza operatia de extragere din coada a elementului de prioritate minima.

Exista multe aplicatii ale cozilor cu prioritate. De exemplu, sa presupunem ca exista o imprimanta in retea. Mai multe calculatoatoare trimit documente cu o anumita prioritate spre a fi listate. Cum imprimanta nu poate listam mai multe documente in acelasi timp, trebuie sa selecteze documentul cu prioritate maxima. In momentul in care a fost listat, documentul este extras, selectandu-se un nou document de prioritate maxima. Astfel, documentele vor fi organizate sub forma unei cozi cu prioritate.

O alta aplicatie reprezentativa este planificarea executiei programelor pe un calculator: coada cu prioritate retine programele ce trebuie sa fie executate in functie de prioritatile lor relative. Cand se incheie sau se intrerupe executia unui program, programul cu cea mai mare prioritate din coada este selectat si lansat in executie (operatia ExtractMax). Adaugarea unui nou program in coada se realizeaza cu operatia Insert.

Exista diverse modalitati de a implementa o coada cu prioritate: ca un vector, ca o lista inlantuita, ordonata sau nu etc. Fiecare dintre aceste variante optimizeaza una dintre cele doua operatii, cealalta realizandu-se in timp liniar.
O structura de date simpla ce permite implementarea ambelor operatii in timp logaritmic este heap-ul. Astfel, pentru operatia Insert se foloseste functia InsertHeap iar pentru operatia ExtractMax se foloseste functia ExtractHeap.

Heap Interactiv :: Contact ::