Kolejka priorytetowa
Z Wikipedii
Kolejka priorytetowa (ang. priority queue) – struktura danych służąca 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 | Tablica asocjacyjna |
|---|---|---|
| Wstawienie elementu | O(lg(n)) | O(1) |
| Dostęp do maksymalnego elementu | O(1) | O(m) |
| Usunięcie maksymalnego elementu | O(lg(n)) | O(m) |
| Dostęp/usunięcie dowolnego elementu | O(n) | O(n + m) |
gdzie:
- n - liczba elementów w kolejce
- m - liczba priorytetów
