Kolejka priorytetowa - wprowadzenie
1. Czym jest kolejka priorytetowa?
Kolejka priorytetowa (priority queue) to struktura danych, w której elementy są obsługiwane według priorytetu, a nie kolejności dodawania.
Różnica vs zwykła kolejka:
| Kolejka FIFO | Kolejka priorytetowa |
|---|---|
| Pierwszy in, pierwszy out | Najwyższy priorytet out |
| Kolejność dodawania | Priorytet |
| Przykład: kolejka w sklepie | Przykład: izba przyjęć szpitala |
Analogia ze świata rzeczywistego:
Izba przyjęć w szpitalu: - Pacjenci są obsługiwani według pilności, nie kolejności przyjścia - Złamana noga (wysoki priorytet) przed przeziębieniem (niski priorytet) - Nowy pacjent z zawałem (najwyższy priorytet) jest obsługiwany natychmiast
2. Podstawowe operacje
| Operacja | Opis | Złożoność* |
|---|---|---|
| insert(x) | Dodaje element z priorytetem | O(log n) |
| extract_max() / extract_min() | Usuwa element o najwyższym/najniższym priorytecie | O(log n) |
| peek() | Zwraca element o najwyższym priorytecie | O(1) |
| is_empty() | Sprawdza, czy kolejka jest pusta | O(1) |
*przy użyciu kopca (heap)
3. Implementacja "naiwna" z listą
UWAGA: Niewydajne, tylko w celach edukacyjnych!
Problem: extract_min() to O(n) – bardzo wolne!
4. Implementacja z użyciem kopca (heap)
Kopiec binarny (binary heap) to drzewo binarne z własnością: - Min-heap: Rodzic ≤ dzieci (najmniejszy na górze) - Max-heap: Rodzic ≥ dzieci (największy na górze)
Python ma wbudowany moduł heapq – implementacja min-heap.
4.1. Podstawowa implementacja
Użycie:
5. Problem: Elementy o tym samym priorytecie
Co jeśli dwa elementy mają ten sam priorytet?
Rozwiązanie: Dodaj licznik
Teraz działa poprawnie:
6. Max-heap (największy element na górze)
heapq to min-heap, ale możemy symulować max-heap negując priorytety:
Użycie:
7. Praktyczne zastosowania
7.1. System kolejkowania zadań
7.2. Izba przyjęć w szpitalu
7.3. Algorytm Dijkstry – najkrótsza ścieżka
7.4. Łączenie k posortowanych list
7.5. Top K najczęstszych elementów
8. Porównanie implementacji
| Implementacja | Insert | Extract | Peek | Zalety |
|---|---|---|---|---|
| Lista | O(1) | O(n) | O(n) | Prosta (ale wolna!) |
| Sortowana lista | O(n) | O(1) | O(1) | Szybki extract (wolny insert) |
| Kopiec (heap) | O(log n) | O(log n) | O(1) | ⭐ Zbalansowana wydajność |
| BST | O(log n)* | O(log n)* | O(log n)* | Może degenerować do O(n) |
*przy drzewie zrównoważonym
Rekomendacja: Używaj kopca (heapq) w praktyce!
9. Złożoność czasowa i pamięciowa
Z użyciem kopca (heap):
| Operacja | Złożoność |
|---|---|
insert(x) |
O(log n) |
extract_min() |
O(log n) |
peek() |
O(1) |
is_empty() |
O(1) |
heapify(list) |
O(n) |
Złożoność pamięciowa:
- O(n) – gdzie n to liczba elementów
10. Budowanie kopca z listy (heapify)
UWAGA: heapify() to O(n), nie O(n log n)!
11. Operacje dodatkowe w heapq
11.1. n najmniejszych/największych elementów
11.2. Z kluczem
12. Własna implementacja kopca binarnego
Dla celów edukacyjnych:
13. Podsumowanie
Kolejka priorytetowa to kluczowa struktura danych:
- Elementy obsługiwane według priorytetu
- Implementacja na kopcu: O(log n)
- Szeroko wykorzystywana w algorytmach
- Python: moduł
heapq
Kluczowe zastosowania:
- Algorytm Dijkstry (najkrótsza ścieżka)
- Harmonogramowanie zadań
- Symulacje zdarzeń
- Łączenie k posortowanych list
- Top K problemów
Kiedy używać kolejki priorytetowej:
- Potrzebujesz dostępu do min/max w O(1)
- Dynamiczne dodawanie i usuwanie
- Obsługa według priorytetu
- Algorytmy grafowe
- Harmonogramowanie
Co dalej warto poznać:
- Kopce (heap sort, d-ary heap)
- Algorytm Dijkstry i A*
- Fibonacci heap (zaawansowane)
- Binomial heap
- Mediana strumienia danych (two heaps)