Ред са приоритетом

У рачунарству, ред са приоритетом је апстрактан тип података, који је сличан регуларном реду или стеку, али који додатно има придружен приоритет сваком елементу. У реду са приоритетом, елемент са највећим приоритетом се узима пре елемента са нижим приоритетом. Ако два елемента имају исти приоритет, онда се узимају на основу његовог положаја у листи.

Ред са приоритетом се углавном имплементира преко хипа, али се концептуално разликује од њега. Ред са приоритетом је апстрактан концепт као "листа" или "мапа"; као што листа може бити имплементирана као повезана листа или као низ, ред са приоритетом може бити имплементиран преко хипа или преко других метода као што је неуређен низ.

Операције

Ред са приоритетом има следеће операције:

insert_with_priority (убаци са приоритетом): додаје елемент у ред са придруженим приоритетом.

pull_highest_priority_element (извади елемент са највећим приоритетом): уклања елемент из реда са највећим приоритетом, и враћа га.

Ова операција је такође позната као "pop_element(Off)","get_maximum_element" или "get_front(most)_element". Неке конвенције обрћу ред приоритета, подразумевајући да ниже вредности имају највиши приоритет, па ова операција може бити позната и као "get_minimum_element", у литератури се често назива као "get_min". Ова операција може често бити наведена као две одвојене функције: "peek_at_highest_priority" и "delete_element", чијим се комбиновањем добија "pull_highest_priority_element".

Операција peek (у овом контексту се назива и find_max (пронаћи максимум) или find_min (пронаћи минимум)), која враћа елемент са највишим приоритетом, али не модификује ред, се веома често имплементира, и скоро увек се извршава у времену О(1). Ова операција и њено извршавање је од великог значаја за велики број употреба реда са приоритетом.

Напредније имплементације могу захтевати компликованије операције, као што је pull_lowest_priority_element(извади елемент са најнижим приоритетом), тражење неколико елемената са највишим или најнижим приоритетом, чишћење реда, чишћење подгрупа реда, обављање гомиле убацивања, спајање два или више редова у један, инкрементирање вредности приоритета било ког елемента итд.

Сличност са редовима

Ред са приоритетом се може посматрати као модификован ред, али када се узме следећи елемент реда прво се враћа елемент са највишим приоритетом. Стек и ред могу бити моделовани као посебне врсте редова са приоритетима. За подсећање, ево како се понашају стек и ред:

Стек- структура која функционише на принципу LIFO(last in, first out), тј. последњи елемент који је убачен на врх стека се први извлачи. Приоритет сваког убаченог елемента монотоно расте. (пример: гомила папира)
: Операције:
: * push- додаје елемент на врх стека (сложеност О(1)).

: * pop- скида елемент са врха стека (сложеност О(1)).

Ред- структура која функционише на принципу FIFO (first in, first out), тј. елемент који је први убачен у ред се први извлачи. Приоритет сваког убаченог елемента монотоно опада. (пример: ред у кафетерији)
: Операције:
: * add- додаје елемент на крај реда (сложеност О(1)).

: * get- скида елемент са почетка реда (сложеност О(1)).

Имплементације

Наивна имплементација

Постоји низ једноставних, обично неефикасних, начина имплементације реда са приоритетом. Оне пружају могућност разумевања реда са приоритетом. На пример, једна имплементација би била, чувати све елементе у неуређеној листи. Када се захтева елемент са највишим приоритетом, пролази се кроз све елементе листе док се не нађе онај са највећим приоритетом. Сложеност, у нотацији велико О: О(1) потребно време за убацивање елемента, О(n) време потребно за претрагу кроз ред.

Уобичајена имплементација

Да би се побољшале перформансе, редови са приоритетом обично користе хип, дајући сложеност О(log n) за операције уношења и брисања и O(n) за поновно изграђивање. Варијанте базичног хипа, као што су упаривање хипова или Фибоначијеви хипови могу да омогуће боље извршавање за неке операције.^[1]

Алтернативно, ако се користи балансирано бинарно стабло претраге, убацивање и брисање ће такође узети О(log n) времена, иако израда стабла од постојећих секвенци узима O(n log n) времена. Ово је типично када већ постоји приступ овим структурама података, као што је стандардна библиотека.

Такође треба приметити, да са тачке гледишта компјутерске сложености, ред са приоритетом се подудара са алгоритмима за сортирање.

Специјални хипови

Постоји неколико специјалних хип структура података које, било да обезбеђују додатне операције или боље извршавање хипа, су базиране на имплементацији специфичних типова кључева посебно целобројних кључева.

Када је скуп кључева {1, 2, ..., C}, и од операција се користе insert (убаци), find-min (пронаћи најмањи) и extract-min (извадити најмањи), ограничен високо приоритетан ред може бити конструисан као низ од С повезаних листа који има показивач на врх (top), у почетку иницијализован на С. Убацивањем члана са кључем k, ставља га на k-то место, и ажурира показивач top, top = min(top, k). Обе ове операције захтевају константно време извршавања. Extract-min брише и враћа један члан листе са индексом top, онда инкрементира (повећава за 1) показивач top, ако је потребно, све док не показује на непразну листу. Ово захтева О(С) времена у најгорем случају. Ова врста редова је корисна за сортирање чворова графа на основу њиховог степена.^[2]
За скуп кључева {1, 2, ..., C}, ван Емде Боас стабло (eng. van Emde Boas tree) подржава операције minimum (минимум), maximum (максимум), insert (убаци), delete (обриши), search (претражи), extract-min (извуци минимални елемент), extract-max (извуци максимални елемент), predecessor(претходник) и successor (следбеник) у O(log log C) времену, али просторна сложеност за мале редове је О(2m/2), где је m број битова у вредности приоритета.^[3]
Алгоритам Фузионог стабла(eng. Fusion tree algorithm), осмишљеног од стране Мајкл Фредмана (Michael Fredman) и Ден Виларда (Dan Willard), имплементира операцију minimum у времену О(1), а операције insert и extract-min у $O({\sqrt {\log n}})$ времену, како наводе аутори:

"Наши алгоритми имају само теоријску функцију; Константни фактори који су укључени у време извршавања спречавају практичност."^[4]

За апликације које извршавају превише "peek" операција за сваку "extract-min" операцију, време комплексности за peek акције може бити редуковано на сложеност О(1) за сва стабла и за хип имплементацију, кеширањем елемента са највећим приоритетом после сваког уметања и брисања. За операцију убацивања, која доприноси највише константном трошку, последњи убачен елемент се пореди једино са претходно кешираним елементом. Операција брисања, која највише доприноси трошку за "peek" операцију (јефтинија је од операције брисања), на временску сложеност није посебно утицала. Монотони ред са приоритетом је специјална врста реда која је оптимизована за случајеве где ниједна ставка икада уметнута нема нижи приоритет од било ког члана претходно екстракованог. Ово ограничење се среће у неколико практичних примена редова са приоритетом.

Једнакост приоритетних редова и алгоритама за сортирање

Коришћење реда са приоритетом за сортирање

Семантика приоритетних редова природно наговештава метод за сортирање: убацити све елементе који ће бити сортирани у ред са приоритетом и редом их избацивати; они ће излазити у сортираном поретку. Ова метода за сортирање је еквивалентна следећим алгоритмима за сортирање:

Име	Имплементација реда са приоритетом	Најбоља	Просечна	Најгора
Хипсорт	Хип	$nlog(n)$	$nlog(n)$	$nlog(n)$
Смутсорт	Леонардо хип	$n$	$nlog(n)$	$nlog(n)$
Сортирање селекцијом	Неуређен низ	$n^{2}$	$n^{2}$	$n^{2}$
Сортирање уметањем	Уређен низ	$n$	$n^{2}$	$n^{2}$
Сортирање уз помоћ бинарног стабла	Самобалансирајуће бинарно стабло претраге	$nlog(n)$	$nlog(n)$	$nlog(n)$

Коришћење алгоритма за сортирање за прављење реда са приоритетом

Алгоритам за сортирање може бити употребљен за имплементацију реда са приоритетом. Нарочито Торуп (eng. Thorup) је рекао:^[5]

"Ми представљамо опште линеарно смањење простора од редова са приоритетом до сортирања, што подразумева да можемо сортирати n кључева у времену S(n) по кључу, затим постоје редови са приоритетом који подржавају операције брисања и убацивања у времену О(S(n)) и операцију наћи минимум (find-min) у константном времену."

То значи да ако постоји алгоритам који може да сортира у времену О(Ѕ) по кључу, где је Ѕ нека функција од n и дужине речи (word size),^[6] онда се може користити дати поступак за креирање реда са приоритетом, где се операција извлачења елемента са највећим приоритетом извршава у времену О(1), а операција убацивања нових елемената (као и брисање елемената) у времену О(Ѕ). На пример, ако се неки алгоритам за сортирање извршава у О(n log log n) времену, може се креирати ред са приоритетом код кога су операција извлачења елемента у О(1), а операција убацивања у О(log log n) времену.

Библиотеке

Ред са приоритетом се често посматра као контејнер тип података (енг. container data structure). Стандардна библиотека шаблона (енг. Standard Template Library (STL)) и С++ 1998 стандард прецизира ред са приоритетом као један контејнер адаптер класе шаблона из Стандардне библиотеке шаблона. Он имплементира максимални ред са приоритетом и има 3 параметра: објекат који се пореди за сортирање као функтор (подразумевано мање <Т> ако је неодређено), основни контејнер за складиштење типова података и два итератора на почетку и на крају низа. За разлику од стварног контејнера из Стандардне библиотеке шаблона, овај контејнер не дозвољава понављање својих елемената (стриктно се придржава своје апстрактне дефиниције типа података).

Стандардна библиотека шаблона такође има корисну функцију за манипулацију другог случајно изабраног контејнера као бинарни максимални хип (max-hip).

Boost (у С++ библиотекама) такође има имплементацију у библиотечком хипу.

Јаvа библиотека садржи класу реда са приоритетом која имплементира минимални ред са приоритетом.

Go-ова библиотека садржи контејнер/хип модул који имплементира min-heap на врх било које компатибилне структуре података.

Стандардна PHP Библиотека (енг. Standard PHP Library) садржи класу SplPriorityQueue.

Apple-ов оквир Core Foundation, садржи CFBinaryHeap структуру која имплементира min-heap.

Апликације

Управљање протоком

Ред са приоритетом се може користити за управљање ограничених ресурса као што су проток на преносној линији од мрежног рутера. У случају одлазећег саобраћаја, у реду због недовољног протока, сви остали редови могу бити заустављени како би слали саобраћај од оног са највећим приоритетом па долазећем. Ово обезбеђује да саобраћај коме су дати приоритети, се доставља са најмање кашњења, и најмања вероватноћа од одбацивања због реда достиже свој максимални капацитет. Сав остали саобраћај може бити решен када је највише приоритетан ред празан.

Други приступ користи се за слање несразмерно више саобраћаја од виших редова са приоритетом.

Многи модерни протоколи за локалне мреже такође укључују концепт приоритетних редова у контроли приступа медијима (енг. media acces control (MAC)), како би осигурали да високо приоритетне апликације (као што су VoIp или IPTV), доживљавају мању скривеност од других апликација које могу бити постављене као мрежни сервис, који не обезбеђује никакве гаранције о томе да ли је податак достављен на адресу (енг. best effort service). Примери укључују IEEE 802.11e (амандман на IEEE 802.11 који обезбеђује перформансе мреже које могу бити виђене од стране корисника мреже (енг.qualiy of service)) и ITU-T G.hn (стандард за брзу локалну мрежу која користи постојеће кућне каблове (далеководе, телефонске линије и коаксијалне каблове)).

Обично ограничење је постављено да ограничи проток који саобраћај од реда са приоритетом може да преузме, како би се спречило гушење остале мреже од пакета високог приоритета. Ово ограничење, обично, никада не постиже висок ниво контроле, као Cisci Callmanager, који може бити програмиран да спречи позиве који могу премашити ограничење програмираног протока.

Симулације дискретних догађаја

Друга употреба реда са приоритетом је да управља догађајима у дискретној симулацији догађаја (енг. discrete event simulation). Догађаји се додају у ред са својим временом симулације, које се користи као приоритет. Извршење симулација приходи понављањем извлачења са врха реда и извршавање догађаја на томе.

Дијкстрин алгоритам

Када је граф меморисан у форми листе суседства или матрице, ред са приоритетом може бити употребљен за ефикасно извлачење минимума помоћу Дијкстрин алгоритма, мада такође је потребна способност да ефикасно мења приоритет одређеног чвора у реду са приоритетом.

Хофманово кодирање

Хофманово кодирање захтева да један ред стално добија два стабла са најнижом фреквенцијом. Приоритетан ред чини ово ефикасним.

Најбољи-први алгоритам

Најбољи-први (енг. Best-first) алгоритам, као А* алгоритам, тражи најкраћи пут између два чвора тежинског графа, испробавајући прво највише обећавајуће путеве. Ред са приоритетом се користи за праћење неистражених путева; један за коју процена (доње границе у случају А* алгоритма) дужине укупне путање је најмања, добија највиши приоритет. Ако ограничење меморије прави најбољи-први алгоритам непрактичним, могу се употребити варијанте као што је SMA* алгоритам, који користи приоритетни ред са два краја (енг. double-ended priority queue), како би допустио уклањање чланова ниског приоритета.

ROAM триангулација алгоритам

Оптимално прилагођавање мрежа у реалном времену (енг. The Real-time Optimally Adapting Meshes (ROAM)) алгоритам израчунава динамичко мењање триангулације једног терена.

Ради на принципу поделе на троуглове, где је потребно више детаља, а на принципу спајања троуглова где је потребно мање детаља. Алгоритам додељује сваком троуглу на терену приоритет, обично се повезује за смањење грешке ако се тај троугао подели. Алгоритам користи два реда са приоритетом, један за троуглове који могу бити подељени и други за троуглове који могу бити спојени. У сваком кораку троугао, из реда у којем су троуглови за поделу, са највишим приоритетом се дели, или троугао из другог реда са најнижим приоритетом се спаја са суседним троугловима.

Примов алгоритам за минимално разапињуће стабло

Користећи min-heap у Примовом алгоритму за проналажење минималног разапињућег стабла повезаног и неусмереног графа, може се постићи добро време извршавања. Min-heap ред користи min-heap структуру података која подржава операције kао што су: insert (убаци), minimum (минимум), extract-min (извући минимални елемент), dесrease-key (смањити кључ).^[7] У овој имплементацији, тежина грана одређује приоритет чворова.^[8]

Додатна литература

Introduction to algorithms. Thomas H. Cormen, Thomas H. Cormen (2nd ed изд.). Cambridge, Mass.: MIT Press. 2001. ISBN 0-262-03293-7. OCLC 46792720. Section 6.5: Priority queues. стр. 138—142.

Референце

^ Introduction to algorithms. Thomas H. Cormen, Thomas H. Cormen (2nd ed изд.). Cambridge, Mass.: MIT Press. 2001. стр. 476—497. ISBN 0-262-03293-7. OCLC 46792720.
^ Skiena 2010, стр. 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 (на језику: енглески). 54 (6): 28. ISSN 0004-5411. doi:10.1145/1314690.1314692.
^ Demaine, Erik. „Lecture 17 — April 18, 2007” (PDF). Приступљено 21. 3. 2022.
^ Introduction to algorithms. Thomas H. Cormen (3rd ed., Eastern economy ed изд.). New Delhi: PHI Learning Private Ltd. 2010. стр. 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”
^ „Prim's Algorithm”. Geek for Geeks. Приступљено 12. 9. 2014.

Литература

Skiena, Steven (2010). The Algorithm Design Manual (2nd изд.). 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 изд.). MIT Press and McGraw-Hill. стр. 476-497. ISBN 978-0-262-03293-3.

Спољашње везе

Descriptions by Lee Killough
PQlib Архивирано на сајту Wayback Machine (10. септембар 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 изд.). Cambridge, Mass.: MIT Press. 2001. стр. 476—497. ISBN 0-262-03293-7. OCLC 46792720.

[FOOTNOTESkiena2010374-2] Skiena 2010, стр. 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 (на језику: енглески). 54 (6): 28. ISSN 0004-5411. doi:10.1145/1314690.1314692.

[6] Demaine, Erik. „Lecture 17 — April 18, 2007” (PDF). Приступљено 21. 3. 2022.

[CLR-7] Introduction to algorithms. Thomas H. Cormen (3rd ed., Eastern economy ed изд.). New Delhi: PHI Learning Private Ltd. 2010. стр. 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”

[GEEKS-8] „Prim's Algorithm”. Geek for Geeks. Приступљено 12. 9. 2014.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]