Red sa prioritetom

U računarstvu, red sa prioritetom je apstraktan tip podataka, koji je sličan regularnom redu ili steku, ali koji dodatno ima pridružen prioritet svakom elementu. U redu sa prioritetom, element sa najvećim prioritetom se uzima pre elementa sa nižim prioritetom. Ako dva elementa imaju isti prioritet, onda se uzimaju na osnovu njegovog položaja u listi.

Red sa prioritetom se uglavnom implementira preko hipa, ali se konceptualno razlikuje od njega. Red sa prioritetom je apstraktan koncept kao "lista" ili "mapa"; kao što lista može biti implementirana kao povezana lista ili kao niz, red sa prioritetom može biti implementiran preko hipa ili preko drugih metoda kao što je neuređen niz.

Operacije

Red sa prioritetom ima sledeće operacije:

insert_with_priority (ubaci sa prioritetom): dodaje element u red sa pridruženim prioritetom.

pull_highest_priority_element (izvadi element sa najvećim prioritetom): uklanja element iz reda sa najvećim prioritetom, i vraća ga.

Ova operacija je takođe poznata kao "pop_element(Off)","get_maximum_element" ili "get_front(most)_element". Neke konvencije obrću red prioriteta, podrazumevajući da niže vrednosti imaju najviši prioritet, pa ova operacija može biti poznata i kao "get_minimum_element", u literaturi se često naziva kao "get_min". Ova operacija može često biti navedena kao dve odvojene funkcije: "peek_at_highest_priority" i "delete_element", čijim se kombinovanjem dobija "pull_highest_priority_element".

Operacija peek (u ovom kontekstu se naziva i find_max (pronaći maksimum) ili find_min (pronaći minimum)), koja vraća element sa najvišim prioritetom, ali ne modifikuje red, se veoma često implementira, i skoro uvek se izvršava u vremenu O(1). Ova operacija i njeno izvršavanje je od velikog značaja za veliki broj upotreba reda sa prioritetom.

Naprednije implementacije mogu zahtevati komplikovanije operacije, kao što je pull_lowest_priority_element(izvadi element sa najnižim prioritetom), traženje nekoliko elemenata sa najvišim ili najnižim prioritetom, čišćenje reda, čišćenje podgrupa reda, obavljanje gomile ubacivanja, spajanje dva ili više redova u jedan, inkrementiranje vrednosti prioriteta bilo kog elementa itd.

Sličnost sa redovima

Red sa prioritetom se može posmatrati kao modifikovan red, ali kada se uzme sledeći element reda prvo se vraća element sa najvišim prioritetom. Stek i red mogu biti modelovani kao posebne vrste redova sa prioritetima. Za podsećanje, evo kako se ponašaju stek i red:

Stek- struktura koja funkcioniše na principu LIFO(last in, first out), tj. poslednji element koji je ubačen na vrh steka se prvi izvlači. Prioritet svakog ubačenog elementa monotono raste. (primer: gomila papira)
: Operacije:
: * push- dodaje element na vrh steka (složenost O(1)).

: * pop- skida element sa vrha steka (složenost O(1)).

Red- struktura koja funkcioniše na principu FIFO (first in, first out), tj. element koji je prvi ubačen u red se prvi izvlači. Prioritet svakog ubačenog elementa monotono opada. (primer: red u kafeteriji)
: Operacije:
: * add- dodaje element na kraj reda (složenost O(1)).

: * get- skida element sa početka reda (složenost O(1)).

Implementacije

Naivna implementacija

Postoji niz jednostavnih, obično neefikasnih, načina implementacije reda sa prioritetom. One pružaju mogućnost razumevanja reda sa prioritetom. Na primer, jedna implementacija bi bila, čuvati sve elemente u neuređenoj listi. Kada se zahteva element sa najvišim prioritetom, prolazi se kroz sve elemente liste dok se ne nađe onaj sa najvećim prioritetom. Složenost, u notaciji veliko O: O(1) potrebno vreme za ubacivanje elementa, O(n) vreme potrebno za pretragu kroz red.

Uobičajena implementacija

Da bi se poboljšale performanse, redovi sa prioritetom obično koriste hip, dajući složenost O(log n) za operacije unošenja i brisanja i O(n) za ponovno izgrađivanje. Varijante bazičnog hipa, kao što su uparivanje hipova ili Fibonačijevi hipovi mogu da omoguće bolje izvršavanje za neke operacije.^[1]

Alternativno, ako se koristi balansirano binarno stablo pretrage, ubacivanje i brisanje će takođe uzeti O(log n) vremena, iako izrada stabla od postojećih sekvenci uzima O(n log n) vremena. Ovo je tipično kada već postoji pristup ovim strukturama podataka, kao što je standardna biblioteka.

Takođe treba primetiti, da sa tačke gledišta kompjuterske složenosti, red sa prioritetom se podudara sa algoritmima za sortiranje.

Specijalni hipovi

Postoji nekoliko specijalnih hip struktura podataka koje, bilo da obezbeđuju dodatne operacije ili bolje izvršavanje hipa, su bazirane na implementaciji specifičnih tipova ključeva posebno celobrojnih ključeva.

Kada je skup ključeva {1, 2, ..., C}, i od operacija se koriste insert (ubaci), find-min (pronaći najmanji) i extract-min (izvaditi najmanji), ograničen visoko prioritetan red može biti konstruisan kao niz od S povezanih lista koji ima pokazivač na vrh (top), u početku inicijalizovan na S. Ubacivanjem člana sa ključem k, stavlja ga na k-to mesto, i ažurira pokazivač top, top = min(top, k). Obe ove operacije zahtevaju konstantno vreme izvršavanja. Extract-min briše i vraća jedan član liste sa indeksom top, onda inkrementira (povećava za 1) pokazivač top, ako je potrebno, sve dok ne pokazuje na nepraznu listu. Ovo zahteva O(S) vremena u najgorem slučaju. Ova vrsta redova je korisna za sortiranje čvorova grafa na osnovu njihovog stepena.^[2]
Za skup ključeva {1, 2, ..., C}, van Emde Boas stablo (eng. van Emde Boas tree) podržava operacije minimum (minimum), maximum (maksimum), insert (ubaci), delete (obriši), search (pretraži), extract-min (izvuci minimalni element), extract-max (izvuci maksimalni element), predecessor(prethodnik) i successor (sledbenik) u O(log log C) vremenu, ali prostorna složenost za male redove je O(2m/2), gde je m broj bitova u vrednosti prioriteta.^[3]
Algoritam Fuzionog stabla(eng. Fusion tree algorithm), osmišljenog od strane Majkl Fredmana (Michael Fredman) i Den Vilarda (Dan Willard), implementira operaciju minimum u vremenu O(1), a operacije insert i extract-min u $O({\sqrt {\log n}})$ vremenu, kako navode autori:

"Naši algoritmi imaju samo teorijsku funkciju; Konstantni faktori koji su uključeni u vreme izvršavanja sprečavaju praktičnost."^[4]

Za aplikacije koje izvršavaju previše "peek" operacija za svaku "extract-min" operaciju, vreme kompleksnosti za peek akcije može biti redukovano na složenost O(1) za sva stabla i za hip implementaciju, keširanjem elementa sa najvećim prioritetom posle svakog umetanja i brisanja. Za operaciju ubacivanja, koja doprinosi najviše konstantnom trošku, poslednji ubačen element se poredi jedino sa prethodno keširanim elementom. Operacija brisanja, koja najviše doprinosi trošku za "peek" operaciju (jeftinija je od operacije brisanja), na vremensku složenost nije posebno uticala. Monotoni red sa prioritetom je specijalna vrsta reda koja je optimizovana za slučajeve gde nijedna stavka ikada umetnuta nema niži prioritet od bilo kog člana prethodno ekstrakovanog. Ovo ograničenje se sreće u nekoliko praktičnih primena redova sa prioritetom.

Jednakost prioritetnih redova i algoritama za sortiranje

Korišćenje reda sa prioritetom za sortiranje

Semantika prioritetnih redova prirodno nagoveštava metod za sortiranje: ubaciti sve elemente koji će biti sortirani u red sa prioritetom i redom ih izbacivati; oni će izlaziti u sortiranom poretku. Ova metoda za sortiranje je ekvivalentna sledećim algoritmima za sortiranje:

Ime	Implementacija reda sa prioritetom	Najbolja	Prosečna	Najgora
Hipsort	Hip	$nlog(n)$	$nlog(n)$	$nlog(n)$
Smutsort	Leonardo hip	$n$	$nlog(n)$	$nlog(n)$
Sortiranje selekcijom	Neuređen niz	$n^{2}$	$n^{2}$	$n^{2}$
Sortiranje umetanjem	Uređen niz	$n$	$n^{2}$	$n^{2}$
Sortiranje uz pomoć binarnog stabla	Samobalansirajuće binarno stablo pretrage	$nlog(n)$	$nlog(n)$	$nlog(n)$

Korišćenje algoritma za sortiranje za pravljenje reda sa prioritetom

Algoritam za sortiranje može biti upotrebljen za implementaciju reda sa prioritetom. Naročito Torup (eng. Thorup) je rekao:^[5]

"Mi predstavljamo opšte linearno smanjenje prostora od redova sa prioritetom do sortiranja, što podrazumeva da možemo sortirati n ključeva u vremenu S(n) po ključu, zatim postoje redovi sa prioritetom koji podržavaju operacije brisanja i ubacivanja u vremenu O(S(n)) i operaciju naći minimum (find-min) u konstantnom vremenu."

To znači da ako postoji algoritam koji može da sortira u vremenu O(Ѕ) po ključu, gde je Ѕ neka funkcija od n i dužine reči (word size),^[6] onda se može koristiti dati postupak za kreiranje reda sa prioritetom, gde se operacija izvlačenja elementa sa najvećim prioritetom izvršava u vremenu O(1), a operacija ubacivanja novih elemenata (kao i brisanje elemenata) u vremenu O(Ѕ). Na primer, ako se neki algoritam za sortiranje izvršava u O(n log log n) vremenu, može se kreirati red sa prioritetom kod koga su operacija izvlačenja elementa u O(1), a operacija ubacivanja u O(log log n) vremenu.

Biblioteke

Red sa prioritetom se često posmatra kao kontejner tip podataka (eng. container data structure). Standardna biblioteka šablona (eng. Standard Template Library (STL)) i S++ 1998 standard precizira red sa prioritetom kao jedan kontejner adapter klase šablona iz Standardne biblioteke šablona. On implementira maksimalni red sa prioritetom i ima 3 parametra: objekat koji se poredi za sortiranje kao funktor (podrazumevano manje <T> ako je neodređeno), osnovni kontejner za skladištenje tipova podataka i dva iteratora na početku i na kraju niza. Za razliku od stvarnog kontejnera iz Standardne biblioteke šablona, ovaj kontejner ne dozvoljava ponavljanje svojih elemenata (striktno se pridržava svoje apstraktne definicije tipa podataka).

Standardna biblioteka šablona takođe ima korisnu funkciju za manipulaciju drugog slučajno izabranog kontejnera kao binarni maksimalni hip (max-hip).

Boost (u S++ bibliotekama) takođe ima implementaciju u bibliotečkom hipu.

Java biblioteka sadrži klasu reda sa prioritetom koja implementira minimalni red sa prioritetom.

Go-ova biblioteka sadrži kontejner/hip modul koji implementira min-heap na vrh bilo koje kompatibilne strukture podataka.

Standardna PHP Biblioteka (eng. Standard PHP Library) sadrži klasu SplPriorityQueue.

Apple-ov okvir Core Foundation, sadrži CFBinaryHeap strukturu koja implementira min-heap.

Aplikacije

Upravljanje protokom

Red sa prioritetom se može koristiti za upravljanje ograničenih resursa kao što su protok na prenosnoj liniji od mrežnog rutera. U slučaju odlazećeg saobraćaja, u redu zbog nedovoljnog protoka, svi ostali redovi mogu biti zaustavljeni kako bi slali saobraćaj od onog sa najvećim prioritetom pa dolazećem. Ovo obezbeđuje da saobraćaj kome su dati prioriteti, se dostavlja sa najmanje kašnjenja, i najmanja verovatnoća od odbacivanja zbog reda dostiže svoj maksimalni kapacitet. Sav ostali saobraćaj može biti rešen kada je najviše prioritetan red prazan.

Drugi pristup koristi se za slanje nesrazmerno više saobraćaja od viših redova sa prioritetom.

Mnogi moderni protokoli za lokalne mreže takođe uključuju koncept prioritetnih redova u kontroli pristupa medijima (eng. media acces control (MAC)), kako bi osigurali da visoko prioritetne aplikacije (kao što su VoIp ili IPTV), doživljavaju manju skrivenost od drugih aplikacija koje mogu biti postavljene kao mrežni servis, koji ne obezbeđuje nikakve garancije o tome da li je podatak dostavljen na adresu (eng. best effort service). Primeri uključuju IEEE 802.11e (amandman na IEEE 802.11 koji obezbeđuje performanse mreže koje mogu biti viđene od strane korisnika mreže (eng.qualiy of service)) i ITU-T G.hn (standard za brzu lokalnu mrežu koja koristi postojeće kućne kablove (dalekovode, telefonske linije i koaksijalne kablove)).

Obično ograničenje je postavljeno da ograniči protok koji saobraćaj od reda sa prioritetom može da preuzme, kako bi se sprečilo gušenje ostale mreže od paketa visokog prioriteta. Ovo ograničenje, obično, nikada ne postiže visok nivo kontrole, kao Cisci Callmanager, koji može biti programiran da spreči pozive koji mogu premašiti ograničenje programiranog protoka.

Simulacije diskretnih događaja

Druga upotreba reda sa prioritetom je da upravlja događajima u diskretnoj simulaciji događaja (eng. discrete event simulation). Događaji se dodaju u red sa svojim vremenom simulacije, koje se koristi kao prioritet. Izvršenje simulacija prihodi ponavljanjem izvlačenja sa vrha reda i izvršavanje događaja na tome.

Dijkstrin algoritam

Kada je graf memorisan u formi liste susedstva ili matrice, red sa prioritetom može biti upotrebljen za efikasno izvlačenje minimuma pomoću Dijkstrin algoritma, mada takođe je potrebna sposobnost da efikasno menja prioritet određenog čvora u redu sa prioritetom.

Hofmanovo kodiranje

Hofmanovo kodiranje zahteva da jedan red stalno dobija dva stabla sa najnižom frekvencijom. Prioritetan red čini ovo efikasnim.

Najbolji-prvi algoritam

Najbolji-prvi (eng. Best-first) algoritam, kao A* algoritam, traži najkraći put između dva čvora težinskog grafa, isprobavajući prvo najviše obećavajuće puteve. Red sa prioritetom se koristi za praćenje neistraženih puteva; jedan za koju procena (donje granice u slučaju A* algoritma) dužine ukupne putanje je najmanja, dobija najviši prioritet. Ako ograničenje memorije pravi najbolji-prvi algoritam nepraktičnim, mogu se upotrebiti varijante kao što je SMA* algoritam, koji koristi prioritetni red sa dva kraja (eng. double-ended priority queue), kako bi dopustio uklanjanje članova niskog prioriteta.

ROAM triangulacija algoritam

Optimalno prilagođavanje mreža u realnom vremenu (eng. The Real-time Optimally Adapting Meshes (ROAM)) algoritam izračunava dinamičko menjanje triangulacije jednog terena.

Radi na principu podele na trouglove, gde je potrebno više detalja, a na principu spajanja trouglova gde je potrebno manje detalja. Algoritam dodeljuje svakom trouglu na terenu prioritet, obično se povezuje za smanjenje greške ako se taj trougao podeli. Algoritam koristi dva reda sa prioritetom, jedan za trouglove koji mogu biti podeljeni i drugi za trouglove koji mogu biti spojeni. U svakom koraku trougao, iz reda u kojem su trouglovi za podelu, sa najvišim prioritetom se deli, ili trougao iz drugog reda sa najnižim prioritetom se spaja sa susednim trouglovima.

Primov algoritam za minimalno razapinjuće stablo

Koristeći min-heap u Primovom algoritmu za pronalaženje minimalnog razapinjućeg stabla povezanog i neusmerenog grafa, može se postići dobro vreme izvršavanja. Min-heap red koristi min-heap strukturu podataka koja podržava operacije kao što su: insert (ubaci), minimum (minimum), extract-min (izvući minimalni element), desrease-key (smanjiti ključ).^[7] U ovoj implementaciji, težina grana određuje prioritet čvorova.^[8]

Dodatna literatura

Introduction to algorithms. Thomas H. Cormen, Thomas H. Cormen (2nd ed izd.). Cambridge, Mass.: MIT Press. 2001. ISBN 0-262-03293-7. OCLC 46792720. CS1 održavanje: Tekst viška (veza) Section 6.5: Priority queues. str. 138—142.

Reference

^ Introduction to algorithms. Thomas H. Cormen, Thomas H. Cormen (2nd ed izd.). Cambridge, Mass.: MIT Press. 2001. str. 476—497. ISBN 0-262-03293-7. OCLC 46792720. CS1 održavanje: Tekst viška (veza)
^ Skiena 2010, str. 374.
^ P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pages 75-84. IEEE Computer Society, 1975.
^ Michael L. Fredman and Dan E. Willard. „Surpassing the information theoretic bound with fusion trees”. Journal of Computer and System Sciences. 48 (3): 533—551. , 1994
^ Thorup, Mikkel (2007). „Equivalence between priority queues and sorting”. Journal of the ACM (na jeziku: engleski). 54 (6): 28. ISSN 0004-5411. doi:10.1145/1314690.1314692.
^ Demaine, Erik. „Lecture 17 — April 18, 2007” (PDF). Pristupljeno 21. 3. 2022. CS1 održavanje: Format datuma (veza)
^ Introduction to algorithms. Thomas H. Cormen (3rd ed., Eastern economy ed izd.). New Delhi: PHI Learning Private Ltd. 2010. str. 634. ISBN 978-81-203-4007-7. OCLC 778716657. „In order to implement Prim's algorithm efficiently, we need a fast way to select a new edge to add to the tree formed by the edges in A. In the pseudo-code” CS1 održavanje: Tekst viška (veza)
^ „Prim's Algorithm”. Geek for Geeks. Pristupljeno 12. 9. 2014.

Literatura

Skiena, Steven (2010). The Algorithm Design Manual (2nd izd.). Springer Science+Business Media. ISBN 978-1-84996-720-4.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). „Fibonacci Heaps”. Introduction to Algorithms (2nd izd.). MIT Press and McGraw-Hill. str. 476-497. ISBN 978-0-262-03293-3.

Spoljašnje veze

Descriptions by Lee Killough
PQlib Arhivirano na sajtu Wayback Machine (10. septembar 2010) - Open source Priority Queue library for C
libpqueue is a generic priority queue (heap) implementation (in C) used by the Apache HTTP Server project.

Best-first search

[1] Introduction to algorithms. Thomas H. Cormen, Thomas H. Cormen (2nd ed izd.). Cambridge, Mass.: MIT Press. 2001. str. 476—497. ISBN 0-262-03293-7. OCLC 46792720. CS1 održavanje: Tekst viška (veza)

[FOOTNOTESkiena2010374-2] Skiena 2010, str. 374.

[3] P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pages 75-84. IEEE Computer Society, 1975.

[4] Michael L. Fredman and Dan E. Willard. „Surpassing the information theoretic bound with fusion trees”. Journal of Computer and System Sciences. 48 (3): 533—551. , 1994

[5] Thorup, Mikkel (2007). „Equivalence between priority queues and sorting”. Journal of the ACM (na jeziku: engleski). 54 (6): 28. ISSN 0004-5411. doi:10.1145/1314690.1314692.

[6] Demaine, Erik. „Lecture 17 — April 18, 2007” (PDF). Pristupljeno 21. 3. 2022. CS1 održavanje: Format datuma (veza)

[CLR-7] Introduction to algorithms. Thomas H. Cormen (3rd ed., Eastern economy ed izd.). New Delhi: PHI Learning Private Ltd. 2010. str. 634. ISBN 978-81-203-4007-7. OCLC 778716657. „In order to implement Prim's algorithm efficiently, we need a fast way to select a new edge to add to the tree formed by the edges in A. In the pseudo-code” CS1 održavanje: Tekst viška (veza)

[GEEKS-8] „Prim's Algorithm”. Geek for Geeks. Pristupljeno 12. 9. 2014.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]