Приоритетна опашка

В компютърните науки приоритетна опашка е абстрактен тип данни, който е като обикновена опашка или стек структура от данни, но допълнително всеки елемент има „приоритет“, свързани с нея. В приоритетна опашка, елемент с висок приоритет се изважда преди такъв с нисък приоритет. Ако два елемента имат еднакъв приоритет, те се изваждат според техния ред на опашката.

Докато приоритетни опашки често се осъществява с купчини, те са концептуално различен от тях. Приоритетна опашка е абстрактно понятие като „списък“ или „карта“. Като списък може да се реализира със свързан списък или масив, приоритетна опашка може да се реализира с купчина или различни други методи като неподреден масив.

Операции

Приоритетна опашка, трябва най-малко да поддържа следните операции:

• добавяне с приоритет – добавят елемент на опашката със съответен приоритет.
• изваждане на елемента с най-висок приоритет – премахнете елемент от опашката, който има най-голям приоритет и го връща. Това е също така известен като „pop_element (Off)“, „get_maximum_element“ или „get_front(most)_element“. Някои конвенции обръщат реда на приоритетите, имайки предвид по-ниските стойности да бъдат с по-висок приоритет, така че това също може да бъде известен като „get_minimum_element“.

В допълнение, 'Peek' (в този контекст често се нарича find-max или find-min), който се връща елемента с най-висок приоритет, но не изменя реда на опашката, е много често използвам, и почти винаги изпълнен за O(1) време. Тази операция и нейното O(1) изпълнението е от ключово значение за много приложения на приоритетните опашки.

По-напреднали приложения на приоритетните опашки могат да се поддържат по-сложни операции, като дърпане на елемента с най-нисък приоритет, разглеждане на първите няколко елемента с най-висок или най-нисък приоритет, изпълнение на групово вмъкване на елементи, сливане на две или повече опашки в една, увеличаване на приоритета на някой елемент и други.

Сходство с опашки

Може да се разглежда приоритетната опашка като модифицирана опашка, но когато се взема следващия елемент от опашката, този с най-висок приоритет се получава първи.

Купчини и опашки могат да бъдат моделирани като определени видове приоритетни опашки. Като напомняне, ето как стекове и опашки се държат: Стек – елемента се дръпна в подредба – последния влязъл излиза първи (например, една купчина документи).

Опашка – елемента се дръпна в подредба – първият влязъл излиза първи (например, реда в кафене).

В стека приоритета на всеки поставен елемент монотонно се увеличава, така последният добавен елемент винаги излиза първи. В опашките приоритета на всеки поставен елемент монотонно се намалява, така първият добавен елемент винаги излиза първи.

Реализация

Наивна реализация

Съществуват много начини за изпълнение на приоритетната опашка, но обикновено неефективни. Те осигуряват аналогия, която да помогне да се разбере какво е приоритетната опашка. Например – може да се държат всички елементи в несортиран списък. Когато елементът с най-голям приоритет е поискан, се търси из всички елементи в списъка за елемента с най-висок приоритет.

Обичайно изпълнение

За подобряване на производителността, приоритетните опашки обикновено използват една купчина за техния скелет, давайки O(log n) производителност за вмъкване и премахване, и O(n) за първоначално построяване.

Алтернативно, когато самобалансиращо двоично дърво за търсене се използва вмъкването и премахване също вземат O(log n) време. Въпреки че построяването на дървета от съществуващи поредици от елементи отнема O(n) време. Това е характерно където вече се има достъп до тези структури от данни, като например с трета страна или стандартни библиотеки.

Имайте предвид, че от гледна точка на изчислителната сложност, приоритетните опашки са подходящи за алгоритмите за сортиране. Вижте следващия раздел за това колко ефективно алгоритмите за сортиране могат да създават ефективни приоритетни опашки.

Изпълнение на приоритетни опашки, използвайки купчини

Стандартният подход за изпълнение на приоритетни опашки, използвайки купчини е да се използва масив (или ArrayList), започвайки от позиция 1 (вместо 0), където всеки елемент в масива съответства на един възел в купчината:

• Коренът на купа е винаги в масив[1].
• Лявото му дете е в масив[2].
• Дясното дете е в масив[3].

По принцип, ако един възел е в масив[к], тогава лявата му дете е в масив[к * 2], и дясното му дете е в масив[к * 2 + 1].

Ако даден възел е в масив [к], то неговият родител е в масив[к / 2] (използва се целочислено деление, така че ако К е нечетно – резултатът е отсечен, например, 3/2 = 1).

Специализирани купчини

Има няколко структури специализирани купчини данни, които или предоставят допълнителни операции, или превъзхождат базираните на купчини реализации за специфични видове ключове, специално целочислени ключове.

• Когато ключовете са {1, 2, ..., C}, и само вмъкване, намери-мин и извличане-мин са нужни, приоритетна опашка с ограничена височина може да се конструира като масив на C свързани списъци плюс указател отгоре – първоначално C. Поставяне на елемент с ключ К добавя елемента към k-тия и обновява най-отгоре ← мин (горе, К), и двете в константно време. извличане-мин изтривания и връща един елемент от списъка с индекс най-отгоре, после инкрементира най-отгоре, ако е необходимо, докато отново сочи към не-празен списък. Това отняма O(C) време в най-лошия случай.
• За ключовете {1, 2, ..., C}, дърво van Emde Boas може да поддържа минималното, максималното, вмъкване, изтриване, търсене, извличане-мин, извличане-макс, предшественик и последващите операции за O(log log C) време, но си има цена – пространство за малки опашки от около O(2 m/2), където m е броят на битовете в приоритетна стойност.
• Алгоритъмът на дърво от Fredman и Willard прилага минималната операцията за O(1) време и поставете и екстракт-мин операции в O (SQRTO(log n)) време, обаче се посочва, от автора, че „Нашите алгоритми имат само теоретичен интерес;.. Постоянните факторите, свързани с времето за изпълнение изключват практичност“.

За приложения, които правят много „Peek“ операции за всяка „екстракт – мин“ операция, сложността за Peek действия може да се намали до O(1) във всички дървесни и куп приложения чрез кеширане на най-висок приоритет елемент след всяко поставяне и премахване. За вмъкване, това добавя най-много постоянна стойност, тъй като нововписаният елемент се сравнява само с предварително кеширания минимум елемент. За изтриване, това най-много добавя допълнителен „Peek“ на разходите, което е типично по-евтино от цената на изтриване, така цялостната сложност на времето не се влияе значително. Монотонни приоритетни опашки са специализирани опашки, които са оптимизирани за случаите, когато нито един предмет вмъкнат има по-нисък приоритет от, който и да е извлечен преди това. Това ограничение се срещна с няколко практически приложения на приоритетни опашки.

Еквивалентност на приоритетните опашки и на алгоритмите за сортиране

Използване на приоритетна опашка за сортиране

Семантиката на приоритетни опашки предлага естествен метод за сортиране: вкарайте всички елементи, които трябва да бъдат сортирани, в приоритетна опашка, и последователно ги премахнете; те ще излязат сортирани. Това всъщност е процедурата, използвана от няколко алгоритъма за сортиране, след като абстракцията, предоставена от приоритетната опашка е отстранена. Този метод за сортиране е еквивалентен на следните алгоритми за сортиране:

Име	Имплементация на приоритетната опашка	Най-добър	Среден	Най-лош
Heapsort	Хийп	nlog(n)	nlog(n)	nlog(n)
Smoothsort	Леонардо хийп	n	nlog(n)	nlog(n)
Selection sort	Несортиран масив	n2	n2	n2
Insertion Sort	Сортиран масив	n2	n2	n2
Tree sort	Самобалансиращо се дърво с двоично търсене	nlog(n)	nlog(n)	nlog(n)

Използване на сортиращ алгоритъм за направата на приоритетна опашка

За имплементацията на приоритетна опашка може да бъде използван сортиращ алгоритъм. Конкретно, Торъп казва:

Представяме общото детерминирано линейно намаляване на пространството в приоритетните опашки като метод на сортиране, което означава, че ако можем да сортираме до n ключа с време за сортиране на всеки от ключовете S(n), тогава е налице приоритетна опашка, позволяваща изтриване и вмъкване на елементи в нея за врене O(S(n)), както и намиране на минимален елемент за константно време.

Това е, ако има алгоритъм за сортиране, който може да се справи със сортирането на всеки ключ за време O(S), където S е някаква функция на n и на размера на думата, а след това този алгоритъм може да използва дадената процедура за създаване на приоритетна опашка, където премахването на елемента с най-висок приоритет отнема O(1) време, и вмъкването на нови елементи (и изтриването на елементи) отнема O(S) време. Например, ако съществува O(n log log n) сортиращ алгоритъм, той може да създаде приоритетна опашка с O(1) време за премахване на елемент и O (log log n) време за вмъкване на елемент.

Библиотеки

Приоритетната опашка често е определяна като структура от данни тип „контейнер“.

Стандартната шаблонна (темплейтна) библиотека (Standard Template Library – STL), и C++ 1998 стандарта, определят приоритетната опашка като един от адаптираните класови шаблони на STL контейнерът. Той имплементира максимална приоритетна опашка, и има три параметъра: обект за сравняване, който се използва за сортиране като функтор например (по подразбиране less<T>), базисният контейнер за съхраняване на структурите от данни (по подразбиране std::vector<T>), и два итератора за началото и края на поредицата. За разлика от действителните STL контейнери, той не позволява итериране през неговите елементи (той се придържа стриктно към неговата абстрактна дефиниция на данните). STL също има полезни функции за манипулиране на друг контейнер със случаен достъп като бинарен max-heap. The Boost (C++ библиотеки) също имат имплементация в стека на библиотеката.

Модулът на Python heapq имплементира двоичен min-heap върху списък.

Библиотеката на Java съдържа класа PriorityQueue, който имплементира минимална приоритетна опашка.

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

Стандартното разширение на PHP библиотеката съдържа класа SplPriorityQueue.

Основния фреймуърк на Apple съдържа структурата CFBinaryHeap, която имплементира min-heap.

Приложения

Управление на честотна лента

Приоритетни опашки може да се използват за да се управляват ограничени ресурси, като например честотната лента на предавателна линия от мрежови рутер. В случаите на натрупване на изходящ трафик поради недостатъчна честотна лента, всички останали опашки могат да бъдат задържани, за да се извърши трафика от опашката с най-висок приоритет веднага след подаването и. Това гарантира, че приоритетния трафик (като данни в реално време, например RTP на VoIP връзка) се предава с възможно най-малко забавяне и също така намалява вероятността да бъде отхвърлен поради достигане на максималния обем на опашката. Останалият трафик може да бъде обработен след като опашката с висок приоритет е празна. Друг подход е да се изпраща непропорционално по-голям трафик от опашките с висок приоритет.

Много съвременни протоколи за локални мрежи също така включват и концепцията за приоритетни опашки при MAC слоя, за да осигурят по-малко забавяне на приложения като VoIP или IPTV в сравнение с други методи. Примери за това са IEEE 802.11e(променена IEEE 802.11, която осигурява quality of service) и ITU-T G.hn (стандарт за високоскоростна локална мрежа, използваща съществуващо обикновено окабеляване (електропроводи, телефонни линии и коаксиални кабели).

Обикновено се въвежда лимит за честотната лента през която минава трафика на опашките с висок приоритет, за да се избегне блокирането на останалите пакети. Този лимит рядко се достига поради контролери на високо ниво, като например Cisco Callmanager, който може да бъде програмиран да задържа заявки, които биха надхвърлили зададения лимит на мрежата.

Симулация на отделни събития

Друго приложение на приоритетните опашки е да се управляват събитията симулация на отделни случаи. Събитията се добавят към опашката с тяхното време, използвано като приоритет. Изпълнението на симулацията се извършва като постоянно се взимат елементи от върха на опашката и се изпълняват събитията от там нататък.

Алгоритъм на Дейкстра

Приоритетната опашка може да се използва при алгоритъма на Дейкстра. Ако графът бъде представен чрез списъци на съседите и за намиране на всеки следващ връх се използва приоритетна опашка.

Кодировка на Хъфман

Кодировката на Хъфман изисква постоянно да бъдат вземани двете дървета с най-ниска честота. Приоритетната опашка прави това ефективно.

Best-first алгоритми за търсене

Best-first алгоритмите, като A* алгоритъма, намират най-краткият път между два върха или разклонения на граф, като първо пробва най-обещаващите маршрути. Приоритетна опашка (позната и като fringe) се използва, за да се следят все още неизползваните маршрути; този, за който очакваната (a lower bound in the case of A*) дължина на пътя и най-кратка, получава най-висок приоритет. Ако ограниченията относно паметта направят best-first търсенето непрактично, варианти като SMA* алгоритъма могат да бъдат използвани с приоритетна опашка, която да позволява махане на елементи с нисък приоритет.

ROAM алгоритъм за триангулация

Алгоритъмът The Real-time Optimally Adapting Meshes (ROAM) изчислява динамично променяща се триангулация на терена. Прилага се, като се отделят подтриъгълници, където е необходимо по-голямо детайлизиране и чрез обединяването им, при изискване за по-малко подробности. Алгоритъмът дава на всеки от триъгълниците приоритет, обикновено свързан с евентуалното намаляване на вероятността за грешка ако този триъгълник бъде разделен на по-малки. Алгоритъмът използва две приоритетни опашки, една за триъгълниците, които могат да бъдат разделени на по-малки и една с тези, които могат да бъдат обединени в по-големи. На всяка стъпка от алгоритъма, триъгълникът от опашката за разделяне с най-висок приоритет се разкъсва на по-малки или съответно триъгълника от опашката за обединяване с най-нисък приоритет се слива със съседните му.