Î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ă.
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.
- 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).
- 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.