Kolejka priorytetowa

Kolejka priorytetowa (ang. priority queue) – abstrakcyjny typ danych służący do przechowywania elementów zbioru, na którym określono relację porządku. Implementacja kolejki priorytetowej przy użyciu kopca charakteryzuje się bardzo szybkim ($O(1)$) dostępem do elementu maksymalnego. Najczęściej kolejkę priorytetową realizuje się za pomocą kopca lub tablicy asocjacyjnej, która mapuje wartość priorytetu na listę wartości z tym priorytetem.

Kolejka priorytetowa ma zastosowanie tam, gdzie obiekty są pobierane z dynamicznej struktury i przetwarzane w kolejności od obiektu o najwyższym priorytecie do obiektu o najniższym priorytecie. Przy czym, w trakcie procesu przetwarzania nowe obiekty mogą być dodawane do kolejki.

W jądrze systemu operacyjnego Linux zastosowana jest kolejka priorytetowa w module szeregującym procesy. Kolejka została zaimplementowana przy użyciu tablicy.

Złożoność obliczeniowa podstawowych operacji:

Operacja	Kopiec (binarny)	Kopiec dwumianowy	Tablica	Lista	Równoważone BST	Kopiec Fibonacciego	Kolejka Brodala
Wstawienie elementu	$O(\log n)$	$O(\log n)$. zamortyzowane: $O(1)$	$O(1)$	$O(1)$	$O(\log n)$	$O(1)$	$O(1)$
Dostęp do elementu minimalnego	$O(1)$	$O(\log n)$ albo $O(1)$	$O(m)$	$O(n)$	$O(\log n)$ albo $O(1)$	$O(1)$	$O(1)$
Usunięcie elementu minimalnego	$O(\log n)$	$O(\log n)$	$O(m)$	$O(n)$	$O(\log n)$	$O(\log n)$ - zamortyzowane	$O(\log n)$
Dostęp/usunięcie dowolnego elementu	$O(n)$	$O(n)$	$O(n+m)$	$O(n)$	$O(\log n)$	$O(\log n)$ - zamortyzowane	$O(\log n)$
Złączenie dwóch kolejek	$O(n_1 \log(n_1+n_2))$	$O(\log(\max\{n_1, n_2\}))$	$O(m)$	$O(1)$	$O(n_1 \log(n_1+n_2))$	$O(1)$	$O(1)$
Zmniejszenie priorytetu dowolnego elementu	$O(\log n)$	$O(\log n)$	$O(1)$	$O(n)$	$O(1)$ - zamortyzowane	$O(\log n)$
Stworzenie nowej kolejki z zadanych n elementów	$O(n)$	$O(n)$	$O(m+n)$	$O(n)$	$O(n \log n)$
Stworzenie pustej kolejki	$O(1)$	$O(1)$	$O(m)$	$O(1)$	$O(1)$	$O(1)$	$O(1)$

gdzie:

• n - liczba elementów w kolejce
• m - liczba priorytetów (w przypadku tablicy jest ona zwykle z góry ograniczona)

W przypadku BST oraz kopca dwumianowego, findmin (znajdowanie elementu minimalnego), można łatwo przyśpieszyć do $O(1)$, poprzez zapamiętywanie najmniejszego elementu w kopcu. Wartość ta jest aktualizowane przy dodawaniu elementów do kopca lub usuwanie elementu minimalnego z kopca, bez zwiększania ich złożoności obliczeniowej.