Coada de priorități

Coada de priorități (engleză: priority queue) este o structură de date în care fiecărui element i se asociază un număr întreg, numit prioritate. Principalele operații sunt punerea și extragerea unui element. La extragerea unui element din coadă se alege elementul cu cea mai înaltă prioritate.

În principiu, coada cu priorități poate fi realizată în două moduri: ca listă ordonată în ordinea descrescătoare a priorităților, sau ca arbore de selecție. Dacă este realizată ca listă ordonată, punerea unui element în coada de priorități de lungime n are complexitatea O(n), deoarece este necesar fie să se deplaseze toate elementele situate după el în cazul listei implementate ca tablou, fie să se parcurga toate elementele situate inaintea lui, în cazul listei înlănțuite. Extragerea elementului din coada de priorități are complexitatea O(1) atât la lista-tablou cât și la cea înlănțuită.

Arborele de selecție

Arborele de selecție (engleză: heap) este o coadă de priorități realizată ca arbore binar aproape complet. Fiecare nod al arborelui de selecție are proprietatea că cei doi fii ai lui (dacă ei există) au priorități mai mici decât a lui. Un astfel de arbore de selecție este reprezentat în figura 6, în care s-a considerat că prioritatea maximă este cea corespunzătoare valorii maxime a numărului care o reprezintă (uneori se admite, dimpotrivă, că prioritatea maximă este 0 sau 1 și scade cu creșterea numărului prin care este reprezentată).
 
Observație: În engleză termenul heap este folosit atât pentru arborele de selecție, cât și pentru memoria cu alocare dinamică (cea în care datele și structurile de date sunt indicate prin pointeri sau prin referințe, iar alocarea în memorie a datelor se face în timpul executării programului). Nu trebuie confundate cele două semnificații.


- Figura 6 -

În figura 6, în nodurile arborelui au fost scrise numai prioritățile acestora. Reprezentarea cozii de priorități este dată in două moduri: a - ca arbore de selecție; b - același arbore, implementat ca tablou.

Remarcăm că arborele de selecție este o structură recursivă: fiecare subarbore al său este, de asemenea, un arbore de selecție.

Adăugarea unui element la coada cu priorități

Să urmărim acum etapele operației de punere a unui element într-o astfel de coadă de priorități. Considerăm că dorim să introducem un nou element cu prioritatea 15. Inițial, acest element este pus pe primul loc rămas liber (astfel încât arborele să se mențină aproape complet), ca în figura 7.


- Figura 7 -

Se constată acum că părintele nodului nou adăugat are prioritate mai mică. În consecință, se schimbă între ele elementele din cele două noduri, ajungându-se în situația din figura 8.


- Figura 8 -

Întrucât și în noua poziție prioritatea elementului nou adăugat este inferioară celei din nodul părinte, elementele din cele doua noduri se schimbă între ele, obtinându-se situația din figura 9.


- Figura 9 -

În această poziție, elementul nou adăugat este bine plasat, deoarece părintele nodului respectiv are prioritate superioară. În consecință, adăugarea unui element nou la coada cu priorități s-a încheiat.

Se observă că numărul maxim de permutări necesare pentru propagarea în sus a elementului nou pus în coadă, pâna ajunge la poziția lui corectă, este egal cu înălțimea arborelui. În consecință, complexitatea operației de punere a unui element în coada de priorități este O(log n).

Extragerea unui element din coada cu priorități.

În cazul cozii de priorități, extragerea unui element se poate face numai din capul cozii. Când coada este organizată ca arbore de selecție, elementul care se extrage (de prioritate maximă) este chiar rădăcina arborelui. Sa urmărim etapele extragerii elementului.


- Figura 10 -

În figura 10, elementul din capul cozii (rădăcina arborelui de selecție) a fost extras, iar locul lui a ramas gol. Se pune problema cu ce element trebuie înlocuit. Singurul element disponibil, pentru ca arborele să rămână aproape complet, este ultimul element de pe ultimul nivel. Situația creată după ce acest ultim element a fost adus în locul liber din rădăcină este reprezentată în figura 11.


- Figura 11 -

Se observă că nodul nu este bine plasat, deoarece are un fiu de prioritate superioara. Se schimbă între ele cele două elemente, obținându-se situația din figura 12. Remarcăm că, dacă ambii fii ar fi avut prioritate superioară, s-ar fi ales cel mai mare dintre ei.


- Figura 12 -

Situația se repetă, deoarece și în noua poziție există un fiu de prioritate superioară. Se schimbă elementele respective între ele, ajungându-se în situația din figura 13.


- Figura 13 -

Având în vedere că, în această situație, nu mai există fiu de prioritate superioară, propagarea s-a încheiat.

Se observă că numărul maxim de permutări necesare pentru propagarea în jos a elementului pus în rădăcină, până ajunge pe poziția lui corectă, este cel mult egal cu înălțimea arborelui, deci complexitatea operației de extragere a unui element din coada de priorități este O(log N).

Exemplu: In fișierul ArboreSelectie.java este dat un exemplu de clasă a arborilor de selecție, în care elementele din noduri sunt perechi (prioritate, element), elementele fiind obiecte (Object). Clasa conține atât metode private, cât și metode publice. Perechile (prioritate, element) sunt instanțe ale clasei interioare Entry. Arborele este implementat sub forma unui tablou cu elemente din clasa Entry. Dacă se depășește capacitatea tabloului, se mărește automat capacitatea cu un increment dat.
Un exemplu de aplicație simplă, în care se testează această clasă, este dat în fișierul TestAS.java.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați