Kolejka priorytetowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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.