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