Kolejki priorytetowe (ang. priority queue) służą do reprezentowania zbiorów skończonych, podobnie jak tablice, stosy i kolejki. Cechą szczególną tej struktury jest liniowe uporządkowanie zbioru elementów. Za matematyczny wzorzec kolejki priorytetowej uważana jest tzw. standardowa struktura kolejek priorytetowych, w której kolejka jest po prostu skończonym zbiorem elementów pewnej uporządkowanej liniowo przestrzeni.

Definicja 1.1 Standardową strukturą kolejek priorytetowych nazywamy dwusortowy system algebraiczny

PQ(E) = < PQ È E; min, insert, delmin, empty, £ >,

którego uniwersum składa się ze zbioru elementów (etykiet) E i zbioru PQ skończonych podzbiorów E. Ponadto,

1. zbiór E jest liniowo uporządkowany przez relację £,

2. a operacje struktury są określone dla dowolnego skończonego zbioru X następująco:

min(X) = najmniejszy element zbioru X, o ile X jest niepusty i nieokreślone w pp.

insert(e,X) = {e} È X,

delmin(X) = X \ {min(X) }, gdy X jest niepusty i nieokreślone w pp.

empty(X) = true wttw X jest zbiorem pustym.

Operacja insert pozwala dołączyć nowy element do zbioru. Wynikiem operacji jest zbiór, zatem, jeśli element e należał do zbioru X przed wykonaniem operacji, to wynikiem będzie ten sam zbiór X. Wynikiem operacji min jest element najmniejszy zbioru, będącego argumentem operacji. Jest oczywiste, że wynik zależy nie tylko od zbioru X, ale od definicji relacji £, o której wiemy tylko, że jest liniowym porządkiem. Operacja delmin usuwa element najmniejszy ze względu na przyjęty porządek £. Obie operacje min i delmin są operacjami częściowymi, nieokreślonymi dla zbioru pustego.

Definicja 1.1 określa nie jeden konkretny obiekt, ale całą klasę struktur w zależności od przyjętego zbioru E i od rodzaju porządku liniowego elementów tego zbioru. Zauważmy, że zarówno drzewa binarnych poszukiwań (BST, AVL), jak i kopce są strukturami takiego właśnie typu - zapewniają implementację wszystkich wymienionych w standardowej strukturze kolejek priorytetowych operacji, a organizacja elementów, w zbiorach reprezentowanych przez te drzewa, zależy od przyjętego porządku liniowego.

W wielu zastosowaniach, nie jest istotne, jak dokładnie jest reprezentowany zbiór i jak są zaimplementowane operacje na nim. Zależy nam raczej na konkretnym zestawie operacji, które moglibyśmy wykonać szybko i zgodnie z naszymi intencjami. Korzystając z gotowych bibliotek modułów, procedur czy klas, nie zastanawiamy się nad szczegółami ich implementacji, raczej posługujemy się specyfikacją by sprawdzić, czy zapewniają pożądane cechy.

Ponieważ operacje wymienione w standardowej strukturze kolejek priorytetowych można zaimplementować na wiele różnych sposobów, zajmijmy się wyodrębnieniem ich wspólnych cech, które pozwolą korzystać z nich zamiennie, i w oderwaniu od szczegółów implementacyjnych. Te wspólne cechy pozwolą określić abstrakcyjne pojęcie kolejki priorytetowej, lub inaczej zdefiniować specyfikację kolejek priorytetowych.

Abstrakcyjna struktura kolejek priorytetowych jest systemem algebraicznym, o dwusortowym uniwersum E È PQ, w którym określone są operacje

Oczywiście standardowa struktura kolejek priorytetowych spełnia wszystkie wymienione postulaty, a operacja member(e,q) daje wynik true tylko wtedy, gdy e jest elementem zbioru reprezentowanego przez q. Postulat drugi określa właściwości wyniku operacji min: wszystkie elementy znajdujące się w kolejce priorytetowej q muszą być większe lub równe min(q). Postulat (PQ3) charakteryzuje operację insert: jeśli wykonamy operację insert(e,q), to na pewno e znajduje się w kolejce priorytetowej q i będziemy mogli dotrzeć do tego elementu po pewnej skończonej liczbie kroków (opisanych w algorytmie memeber). Co więcej operacja ta nie modyfikuje innych elementów, które już w q były. Postulat (PQ4) charakteryzuje wykonanie operacji delmin - to element minimalny zostaje w jej wyniku usunięty, a inne elementy, które w kolejce priorytetowej q znajdowały się przed wykonaniem operacji, będą się tam znajdowały i po jej wykonaniu. Ostatni postulat (PQ5) zapewnia, że zbiór dostępnych elementów w dowolnej kolejce priorytetowej jest skończony. Zwróćmy uwagę na algorytmiczne sformułowanie tego postulatu - niestety żadna formuła klasycznej logiki nie może tej własności wyrazić.

Wszystkie postulaty (PQ1) - (PQ5) są też spełnione przez operacje określone w kopcach, w drzewach binarnych poszukiwań i w drzewach AVL. Struktury AVL, BST i kopca są więc przykładami implementacji abstrakcyjnej struktury kolejek priorytetowych.

Można udowodnić więcej: dowolne dwa modele kolejek priorytetowych oparte na tym samym zbiorze elementów E są izomorficzne. Wynika to natychmiast z następującego twierdzenia o reprezentacji stwierdzającego, że każdy model przedstawionej specyfikacji kolejek priorytetowych jest izomorficzny z pewnym modelem standardowym.

Twierdzenie 1.1 (O reprezentacji) Każdy model postulatów (PQ1) - (PQ5) jest izomorficzny z pewnym modelem standardowym kolejek priorytetowych.

Jaka płynie stąd korzyść dla informatyka, programisty? Mając daną konkretną implementację kolejki priorytetowej możemy posługiwać się dostarczonymi operacjami nie wchodząc w szczegóły implementacyjne i uzasadniać poprawność tworzonych nowych algorytmów w oparciu o własności wymienione w postulatach (PQ1)-(PQ5). W następnym punkcie tego wykładu przedstawimy dwie ilustracje takiego podejścia.

Pytanie 1: Jaka jest różnica między kolejką FIFO, a kolejką priorytetową?