# Implementacja std::priority_queue, własne komparatory i zastosowania algorytmiczne
std::priority_queue to adapter kontenera w bibliotece standardowej C++, implementujący strukturę danych kolejki priorytetowej, oparty na kopcu binarnym. Umożliwia efektywne zarządzanie elementami według priorytetu, co jest najważniejsze w wielu algorytmach. W niniejszym artykule szczegółowo omówimy działanie tej struktury, mechanizmy dostosowywania priorytetów oraz praktyczne zastosowania w algorytmice.
Wprowadzenie do std::priority_queue
std::priority_queue jest adapterem kontenera, który wykorzystuje kopiec binarny (zwykle na podstawie std::vector), aby zapewnić stały czas dostępu do elementu o najwyższym priorytecie (domyślnie maksymalnym). Operacje wstawiania (push) i usuwania (pop) działają w czasie logarytmicznym (O(\log n)). Domyślnie elementy są porządkowane z użyciem komparatora std::less, co oznacza, iż top() zwraca największy element. Możliwość zmiany tego zachowania poprzez własne komparatory jest jedną z głównych cech tej struktury.
Mechanizm działania kopca binarnego
Implementacja std::priority_queue opiera się na własnościach kopca binarnego:
- Struktura drzewiasta – kopiec jest drzewem binarnym, gdzie wartość każdego węzła jest większa lub równa wartościom swoich dzieci (właściwość kopca maksymalnego);
- Przechowywanie w tablicy – drzewo kopca jest przechowywane w tablicy (najczęściej std::vector), gdzie:
- indeks rodzica: (parent(i) = ⌊(i-1)/2⌋),
- indeks lewego dziecka: (2i + 1),
- indeks prawego dziecka: (2i + 2).
- Operacje –
- push – element jest dodawany na koniec tablicy, następnie „wynoszony” do góry (ang. sift up), aż przywrócona zostanie adekwatność kopca;
- pop – element top() jest usuwany, a na jego miejsce wstawiany jest ostatni element tablicy, który jest „opuszczany” w dół (ang. sift down).
Przykład operacji push:
std::vector heap = {9, 8, 6, 7, 5, 2, 0}; heap.push_back(4); std::push_heap(heap.begin(), heap.end()); // Wynik: {9, 8, 6, 7, 5, 2, 0, 4}Definiowanie własnych komparatorów
Komparator decyduje o kolejności elementów w kolejce. Może to być:
- Funkcja lub funktor – klasa z operatorem ();
Zastosowanie w priority_queue:
std::priority_queue<Foo, std::vector<Foo>, Compare> pq;- Wyrażenie lambda (C++11+) –
- Dla typów wbudowanych – domyślnie std::less (kolejka maksymalna), kolejka minimalna: std::priority_queue<int, std::vector<int>, std::greater<int>>.
Przykład dla struktury Person:
struct Person { int age; std::string name; }; auto comp = [](Person a, Person b) { return a.age < b.age; }; // Najstarszy na górze std::priority_queue<Person, std::vector<Person>, decltype(comp)> pq(comp);Dynamiczna aktualizacja priorytetów – ograniczenia i rozwiązania
std::priority_queue nie wspiera aktualizacji priorytetów dla elementów już umieszczonych w kolejce. Wynika to z kilku powodów:
- brak powiadomień – kontener nie „wie”, iż wartość elementu uległa zmianie,
- kopiec nie jest automatycznie przebudowywany – po modyfikacji elementu konieczne jest przebudowanie kopca (O(n)).
Rozwiązania:
- Wskaźniki – przechowywanie wskaźników do obiektów zamiast kopii;
- Algorytmy z ponownym wstawianiem – na przykład w algorytmie Dijkstry, po aktualizacji odległości wierzchołek jest ponownie wstawiany do kolejki;
- Rozszerzone struktury danych – __gnu_pbds::priority_queue (GCC) obsługuje modify oraz erase.
Zastosowania algorytmiczne
Algorytm Dijkstry (najkrótsze ścieżki)
Kolejka priorytetowa minimalizuje czas wyboru wierzchołka o najmniejszej odległości:
std::priority_queue<Node, std::vector<Node>, Compare> pq; pq.push({0, start}); while (!pq.empty()) { Node u = pq.top(); pq.pop(); for (auto [v, weight] : adj[u]) if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); // Ponowne wstawienie } }Złożoność: O((E + V) log V).
Algorytm Prima (minimalne drzewo rozpinające)
std::priority_queue<Edge, std::vector<Edge>, Compare> pq; pq.push({0, start}); while (!pq.empty()) { auto [w, u] = pq.top(); pq.pop(); for (auto [v, weight] : adj[u]) if (!inMST[v] && weight < key[v]) { key[v] = weight; pq.push({key[v], v}); } }Złożoność: O(E log V).
Kodowanie Huffmana
Budowa drzewa Huffmana wykorzystuje kolejkę priorytetową do łączenia węzłów o najmniejszej częstotliwości:
std::priority_queue<HNode*, std::vector<HNode*>, Compare> pq; for (auto node : nodes) pq.push(node); while (pq.size() > 1) { auto left = pq.top(); pq.pop(); auto right = pq.top(); pq.pop(); auto parent = new HNode(left->freq + right->freq); pq.push(parent); }Uwaga: wymaga komparatora dla wskaźników.
Scalanie K posortowanych list
auto comp = [](ListNode* a, ListNode* b) { return a->val > b->val; }; std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(comp)> pq(comp); for (auto list : lists) if (list) pq.push(list); while (!pq.empty()) { ListNode* node = pq.top(); pq.pop(); if (node->next) pq.push(node->next); }Złożoność: O(N log K), gdzie N to łączna liczba elementów.
Ograniczenia std::priority_queue
- Brak dostępu do elementów – dostępny jest tylko element top();
- Brak iteratorów – niemożliwe jest przeglądanie elementów kolejki;
- Aktualizacja priorytetów – wymaga stosowania obejść (np. wskaźniki);
- Wydajność – push i pop: O(log n), tworzenie kopca: O(n), brak optymalnej lokalności w cache dla dużych struktur.
Alternatywy i rozszerzenia
- std::set – umożliwia aktualizację (usunięcie i ponowne wstawienie), ale operacje w czasie O(log n) i wyższe zużycie pamięci;
- boost::heap – pairing_heap: obsługuje update oraz decrease_key w czasie O(log n);
- __gnu_pbds::priority_queue (GCC) –
Podsumowanie
std::priority_queue jest potężnym narzędziem do zarządzania danymi według priorytetów, szczególnie efektywnym w implementacji algorytmów grafowych oraz problemów optymalizacyjnych. Pomimo braku wsparcia dla aktualizacji elementów, jego prostota i wydajność są niezastąpione w wielu scenariuszach. Rozszerzenia biblioteczne (takie jak pb_ds dostępne w GCC) oraz kreatywne użycie wskaźników lub ponownego wstawiania pozwalają obejść główne ograniczenia. Kluczową zaletą jest elastyczność w definiowaniu priorytetów dzięki komparatorom, co umożliwia dostosowanie struktury do złożonych typów danych.
Rekomendacje –
- W algorytmach wymagających częstych aktualizacji priorytetów rozważ __gnu_pbds::priority_queue lub boost::heap;
- Dla prostych scenariuszy std::priority_queue z własnymi komparatorami (lambda, funktory) jest optymalnym wyborem;
- Unikaj przechowywania dużych obiektów bezpośrednio – zamiast tego używaj wskaźników.
