In principiu, coada cu prioritati poate fi realizata in doua moduri: ca lista ordonata in ordinea descrescatoare a prioritatilor, sau ca arbore de selectie. Daca este realizata ca lista ordonata, punerea unui element in coada de prioritati de lungime n are complexitatea O(n), deoarece este necesar fie sa se deplaseze toate elementele situate dupa el in cazul listei implementate ca tablou, fie sa se parcurga toate elementele situate inaintea lui in cazul listei inlantuite. Extragerea elementului din coada are complexitatea O(1) atat la lista-tablou cat si la cea inlantuita.
Observatie: In engleza termenul heap este folosit atat pentru arborele de selectie, cat si pentru memoria cu alocare dinamica (cea in care datele si structurile de date sunt indicate prin pointeri sau prin referinte, iar alocarea in memorie a datelor se face in timpul executarii programului). Nu trebuie confundate cele doua semnificatii. |
- Figura 6 -
In figura 6, in nodurile arborelui au fost scrise numai prioritatile acestora. Reprezentarea cozii de prioritati este data in doua moduri: a - ca arbore de selectie; b - acelasi arbore implementat ca tablou.
Remarcam ca arborele de selectie este o structura recursiva: fiecare subarbore al sau este, de asemenea, un arbore de selectie.
- Figura 7 -
Se constata acum ca parintele nodului nou adaugat are prioritate mai mica. In consecinta, se schimba intre ele elementele din cele doua noduri, ajungandu-se in situatia din figura 8.
- Figura 8 -
Intrucat si in noua pozitie prioritatea elementului nou adaugat este inferioara celei din nodul parinte, elementele din cele doua noduri se schimba intre ele, obtinandu-se situatia din figura 9.
- Figura 9 -
In aceasta pozitie elementul nou adaugat este bine plasat, deoarece parintele nodului respectiv are prioritate superioara. In consecinta, adaugarea unui element nou la coada cu prioritati s-a incheiat.
Se observa ca numarul maxim de permutari necesare pentru propagarea in sus a elementului nou pus in coada, pana ajunge la pozitia lui corecta, este egal cu inaltimea arborelui. In consecinta, complexitatea operatiei de punere a unui element in coada de prioritati este O(log n).
- Figura 10 -
In figura 10 elementul din capul cozii (radacina arborelui de selectie) a fost extras, iar locul lui a ramas gol. Se pune problema cu ce element trebuie inlocuit. Singurul element disponibil, pentru ca arborele sa ramana aproape complet, este ultimul element de pe ultimul nivel. Situatia creata dupa ce acest ultim element a fost adus in locul liber din radacina este reprezentata in figura 11.
- Figura 11 -
Se observa ca nodul nu este bine plasat, deoarece are un fiu de prioritate superioara. Se schimba intre ele cele doua elemente, obtinandu-se situatia din figura 12. Remarcam ca, daca ambii fii ar fi avut prioritate superioara, s-ar fi ales cel mai mare dintre ei.
- Figura 12 -
Situatia se repeta, deoarece si in noua pozitie exista un fiu de prioritate superioara. Se schimba elementele respective intre ele, ajungandu-se in situatia din figura 13.
- Figura 13 -
Avand in vedere ca, in aceasta situatie, nu mai exista fiu de prioritate superioara, propagarea s-a incheiat.
Se observa ca numarul maxim de permutari necesare pentru propagarea in jos a elementului pus in radacina, pana ajunge la pozitia lui corecta, este cel mult egal cu inaltimea arborelui, deci complexitatea operatiei de extragere a unui element din coada de prioritati este O(log N).
Exemplu: In fisierul ArboreSelectie.java
este un exemplu de clasa a arborilor de selectie, in care elementele din
noduri sunt perechi (prioritate, element), elementele fiind obiecte (Object).
Clasa contine atat metode private, cat si metode publice. Perechile (prioritate,
element) sunt instante ale clasei interioare Entry. Arborele este implementat
sub forma unui tablou cu elemente din clasa Entry. Daca se depaseste capacitatea
tabloului, se mareste automat capacitatea cu un increment dat.
Un exemplu de aplicatie simpla, in care se testeaza aceasta clasa,
este dat in fisierul TestAS.java.