10 ručno nacrtanih dijagrama: detaljno o Java prioritetnom redu PriorityQueue
Ponovo pozivamo profesora Vanga da izađe na scenu i svima nama održi predavanje o prioritetnom redu PriorityQueue.
PriorityQueue je implementacija prioritetnog reda u Javi zasnovana na prioritetnom heapu; u stanju je da operacije umetanja i brisanja elemenata izvrši u vremenskoj složenosti O(log n) i automatski održava redosled prioriteta elemenata u redu.
Jednostavnije rečeno, PriorityQueue je red, ali ne radi po principu „prvi ušao, prvi izašao”, već sortira elemente prema njihovom prioritetu. Kada u PriorityQueue umetnete element, on automatski, na osnovu prioriteta elementa, umeće element na odgovarajuću poziciju. Kada iz PriorityQueue brišete element, on automatski izbacuje iz reda element sa najvišim prioritetom.
Odozdo👇🏻 je jednostavan primer PriorityQueue:
// Kreiranje objekta PriorityQueue
PriorityQueue<String> priorityQueue = new PriorityQueue<>();
// Dodavanje elemenata u PriorityQueue
priorityQueue.offer("Chenmo Wang Er");
priorityQueue.offer("Čen Ćingjang");
priorityQueue.offer("Siao Đuanling");
// Ispis elemenata iz PriorityQueue
System.out.println("Elementi u PriorityQueue:");
while (!priorityQueue.isEmpty()) {
System.out.print(priorityQueue.poll() + " ");
}U gornjem kodu prvo smo kreirali objekat PriorityQueue i u njega dodali tri elementa. Zatim pomoću while petlje obilazimo elemente PriorityQueue i ispisujemo ih. Pogledajmo izlaz:
Elementi u PriorityQueue:
Siao Đuanling Čen Ćingjang Chenmo Wang ErPogledajmo još jedan primer.
// Kreiranje objekta PriorityQueue i određivanje redosleda prioriteta
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
// Dodavanje elemenata u PriorityQueue
priorityQueue.offer("Chenmo Wang Er");
priorityQueue.offer("Čen Ćingjang");
priorityQueue.offer("Siao Đuanling");
// Ispis elemenata iz PriorityQueue
System.out.println("Elementi u PriorityQueue:");
while (!priorityQueue.isEmpty()) {
System.out.print(priorityQueue.poll() + " ");
}U gornjem kodu smo pomoću metoda Comparator.reverseOrder() odredili da redosled prioriteta u PriorityQueue bude opadajući. Odnosno, elementi u PriorityQueue biće sortirani od najvećeg ka najmanjem.
Ostatak koda je isti kao u prethodnom primeru; pogledajmo ponovo izlaz:
Elementi u PriorityQueue:
Siao Đuanling Chenmo Wang Er Čen ĆingjangAko uporedimo izlaze dva primera, lako je uočiti da je redosled upravo suprotan.
Namena PriorityQueue
Glavna namena PriorityQueue je da održava sortiranost skupa podataka, tako da se pri dohvatanju podataka može postupati po određenom redosledu prioriteta — kada pozovemo metod poll(), on sa vrha reda izbacuje element sa najvišim prioritetom. Ima široku primenu u mnogim scenarijima, kao što su raspoređivanje zadataka, obrada događaja, kao i u algoritmima koji zahtevaju sortiranje podataka.
U praksi se PriorityQueue često koristi za implementaciju algoritama poput Dijkstrinog algoritma, Primovog algoritma i Hafmanovog kodiranja. Ovde ćemo ukratko opisati namenu ovih algoritama; nije problem ako ih ne razumete u potpunosti.
Dijkstrin algoritam je algoritam za izračunavanje najkraćeg puta u težinskom grafu. Algoritam koristi pohlepnu strategiju: pri obilasku grafa, u svakom koraku bira onaj čvor koji je trenutno najbliže izvornom čvoru i iz njega nastavlja širenje, ažurirajući udaljenosti ostalih čvorova. Nakon više navrata širenja dobijaju se najkraći putevi od izvornog čvor do svih ostalih čvorova.
Primov algoritam je algoritam za određivanje minimalnog razapinjućeg stabla; u težinskom povezanom grafu pronalazi razapinjuće stablo kod kojeg je zbir težina svih grana minimalan. Algoritam kreće od proizvoljnog čvora i postepeno povećava veličinu stabla, pri čemu svaki put bira onaj čvor koji je najbliže već izgrađenom stablu i dodaje ga u stablo.
Hafmanovo kodiranje je algoritam kompresije zasnovan na Hafmanovom stablu; služi da niz karaktera pretvori u binarni kod radi kompresije. Glavna ideja algoritma je da se izgradnjom Hafmanovog stabla češće pojavljivanji karakteri predstavljaju kraćim kodom, a ređe pojavljivanji dužim kodom, čime se postiže kompresija niza. Pri dekompresiji se na osnovu koda korak po korak rekonstruiše originalni niz.
Pošto je donja implementacija PriorityQueue zasnovana na heapu, kada je količina podataka velika, upotreba PriorityQueue pruža dobru vremensku složenost.
Ovde se radi o odnosima veličine, a veličinu elemenata može određivati prirodni redosled samog elementa (natural ordering), ali i komparator prosleđen pri konstrukciji (Comparator, ili element sam implementira Comparable interfejs).
U PriorityQueue svaki element ima prioritet koji određuje njegovu poziciju u redu. Red interno pomoću min-heap-a (a može i max-heap-a) održava odnose prioriteta između elemenata. Konkretno, min-heap je potpuno binarno stablo u kojem vrednost bilo kog čvora koji nije list nije veća od vrednosti njegovih levog i desnog potomka, što osigurava da element na vrhu reda (vrh heap-a) uvek bude element sa najvišim prioritetom.
Potpuno binarno stablo (Complete Binary Tree) je binarno stablo u kojem su, osim poslednjeg nivoa, svi nivoi puni, a čvorovi poslednjeg nivoa su poravnati ulevo. Ispod je skica potpunog binarnog stabla:
1
/ \
2 3
/ \ /
4 5 6Heap je potpuno binarno stablo; osobina heap-a je da je vrednost korenog čvora najmanja (min-heap) ili najveća (max-heap), i da vrednost bilo kog čvora koji nije koren nije veća (odnosno nije manja) od vrednosti njegovog roditeljskog čvora.
Ovo je min-heap koji sadrži cele brojeve 1, 2, 3, 4, 5, 6, 7:
1
/ \
2 3
/ \ / \
4 5 6 7Ovo je max-heap.
8
/ \
7 5
/ \ / \
6 4 2 1Pošto je struktura potpunog binarnog stabla pravilna, elemente heap-a može se skladištiti u nizu, bez potrebe za dodatnim prostorom poput pokazivača.
U heap-u se indeks svakog čvora i njegov indeks u nizu jedan prema drugom direktno odnose: ako je indeks čvora i, onda je indeks njegovog roditeljskog čvora i/2, indeks levog potomka 2i, a indeks desnog potomka 2i+1.
Pretpostavimo da imamo niz arr=[10, 20, 15, 30, 40] i da ga sada želimo pretvoriti u min-heap.
Prvo niz raspoređujemo u oblik potpunog binarnog stabla, kao na slici ispod:
10
/ \
20 15
/ \
30 40Odozgo nadole, sleva nadesno, redom označavamo svaki čvor brojem, kao što je prikazano:
1
/ \
2 3
/ \
4 5Zatim, prema gornjim formulama, redom određujemo poziciju svakog čvora u nizu. Na primer, indeks roditeljskog čvora čvora 1 iznosi 1/2=0, indeks levog potomka 21=2, a indeks desnog potomka 21+1=3; dakle čvor 1 u nizu je na poziciji 0, čvor 2 na poziciji 2, a čvor 3 na poziciji 3.
Odgovarajući niz je [10, 20, 15, 30, 40], što zadovoljava definiciju min-heap-a, odnosno vrednost svakog čvora je manja ili jednaka vrednostima njegovih potomaka.
Dobro, nacrtaćemo još jednu sliku da to bolje razumemo.
Na gornjoj slici smo svaki element označili prema redosledu obilaska po nivoima. Ako ste dovoljno pažljivi, primetićete da su oznake roditeljskog i potomačkog čvora međusobno povezane — tačnije, između oznaka roditeljskog i potomačkog čvora važi sledeći odnos:
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2Pomoću ove tri formule lako se izračunavaju indeksi roditeljskog i potomačkih čvorova nekog čvora. Upravo zato se heap može skladištiti direktno u nizu.
Analiza metoda
add() i offer()
add(E e) i offer(E e) imaju isto značenje — oba umeću element u prioritetni red; razlika je samo u tome što Queue interfejs propisuje da ova dva metoda drugačije postupaju pri neuspehu umetanja: prvi baca izuzetak, a drugi vraća false. Za PriorityQueue ova dva metoda zapravo nemaju razlike.
Novo dodatni element može narušiti osobine min-heap-a, pa je potrebno izvršiti odgovarajuće prilagođavanje.
//offer(E e)
public boolean offer(E e) {
if (e == null)//ne dozvoljava se umetanje null elementa
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);//automatsko proširenje
size = i + 1;
if (i == 0)//red je pre bio prazan, ovo je prvi umetnuti element
queue[0] = e;
else
siftUp(i, e);//prilagođavanje
return true;
}U gornjem kodu funkcija proširenja grow() je slična funkciji grow() u ArrayList — jednostavno se zauzme veći niz i u njega prekopiraju elementi originalnog niza, pa o tome nećemo dalje. Važno je obratiti pažnju na metod siftUp(int k, E x), koji umeće element x i pritom održava osobine heap-a.
//siftUp()
private void siftUp(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)//poziva metod poređenja komparatora
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}Postupak prilagođavanja je sledeći: počevši od pozicije koju određuje k, x se sloj po sloj poredi sa parent-om trenutne tačke i razmenjuje sve dok ne bude zadovoljen uslov x >= queue[parent]. Imajte na umu da ovo poređenje može biti po prirodnom redosledu elementa ili po redosledu koji određuje komparator.
element() i peek()
element() i peek() imaju potpuno isto značenje — dohvataju, ali ne brišu element sa početka reda, odnosno onaj element u redu koji ima najmanju vrednost. Jedina razlika je u tome što prvi metod pri neuspehu baca izuzetak, a drugi vraća null. Prema osobinama min-heap-a, element na vrhu heap-a je globalno najmanji; pošto se heap predstavlja nizom, prema odnosu indeksa, element na indeksu 0 istovremeno je i element na vrhu heap-a. Dakle dovoljno je direktno vratiti element na indeksu 0 niza.
I kod je veoma koncizan:
//peek()
public E peek() {
if (size == 0)
return null;
return (E) queue[0];//element na indeksu 0 je najmanji
}remove() i poll()
I remove() i poll() imaju potpuno isto značenje — dohvataju i brišu element sa početka reda; razlika je u tome što prvi metod pri neuspehu baca izuzetak, a drugi vraća null. Pošto operacija brisanja menja strukturu reda, da bi se održale osobine min-heap-a potrebno je izvršiti odgovarajuće prilagođavanje.
Kod izgleda ovako:
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];//element na indeksu 0 je najmanji
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);//prilagođavanje
return result;
}Gornji kod prvo zapisuje element na indeksu 0, zatim elementom sa poslednje pozicije zamenjuje element na indeksu 0, nakon čega poziva metod siftDown() da prilagodi heap, i na kraju vraća prethodni element sa indeksa 0 (odnosno najmanji element). U fokusu je metod siftDown(int k, E x), čija je uloga da počevši od pozicije koju određuje k, x sloj po sloj nadole razmenjuje sa manjim od levog i desnog potomka trenutne tačke, sve dok x ne bude manji ili jednak bilo kom od levog i desnog potomka.
//siftDown()
private void siftDown(int k, E x) {
int half = size >>> 1;
while (k < half) {
//prvo se pronalazi manji od levog i desnog potomka, upisuje u c, a njegov indeks u child
int child = (k << 1) + 1;//leftNo = parentNo*2+1
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;//zatim c zamenjuje prethodnu vrednost
k = child;
}
queue[k] = x;
}remove(Object o)
Metod remove(Object o) briše iz reda jedan element jednak o (ako ih ima više jednakih, briše se samo jedan); ovaj metod ne pripada interfejsu Queue, već interfejsu Collection. Pošto operacija brisanja menja strukturu reda, potrebno je prilagođavanje; a pošto pozicija elementa koji se briše može biti proizvoljna, postupak prilagođavanja je nešto složeniji nego kod ostalih metoda.
Konkretno, remove(Object o) se može podeliti u dva slučaja:
- Briše se poslednji element. Dovoljno je direktno obrisati, bez prilagođavanja.
- Ne briše se poslednji element; od pozicije brisanja, sa zadnjim elementom kao referencom, jednom se poziva
siftDown(). O tome ovde nećemo dalje.
Konkretan kod je sledeći:
//remove(Object o)
public boolean remove(Object o) {
//obilaskom niza pronalazi se indeks prvog elementa koji zadovoljava o.equals(queue[i])
int i = indexOf(o);
if (i == -1)
return false;
int s = --size;
if (s == i) //slučaj 1
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);//slučaj 2
......
}
return true;
}Kratak pregled
PriorityQueue je veoma često korišćena struktura podataka — to je posebna implementacija heap-a (Heap) koja se može koristiti za efikasno održavanje uređenog skupa.
- Njena donja implementacija je niz koji pomoću osobina heap-a održava redosled elemenata.
- Pri dohvatanju elemenata postupa se po redosledu prioriteta (od najmanjeg ka najvećem ili obrnuto).
- Ako je potrebno odrediti sortiranje, elementi moraju implementirati Comparable interfejs ili se mora proslediti Comparator koji vrši poređenje.
Možete vežbati upotrebu PriorityQueue na LeetCode zadatku broj 23: Spajanje K sortiranih listi.
Rešenje zadatka sam već ostavio na tehnološkom portalu, pa možete pogledati kao referencu.
Referentni link: https://github.com/CarpenterLee/JCFInternals, autor: Li Hao, obrada: Chenmo Wang Er