std::priority_queue – implementacja kopca, własne komparatory i zastosowania algorytmiczne

# 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 kluczowe 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, że 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:

1. 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);
2. 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).

1. Operacje –

• push – element jest dodawany na koniec tablicy, następnie „wynoszony” do góry (ang. sift up), aż przywrócona zostanie właściwość 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ć:

1. Funkcja lub funktor – klasa z operatorem ();

struct Compare {
  bool operator()(const Foo& a, const Foo& b) {
    return a.priority > b.priority; // Kolejka minimalna
  }
};

Zastosowanie w priority_queue:

std::priority_queue<Foo, std::vector<Foo>, Compare> pq;

2. Wyrażenie lambda (C++11+) –

auto comp = [](int a, int b) { return a > b; };
std::priority_queue<int, std::vector<int>, decltype(comp)> pq(comp);

3. 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”, że wartość elementu uległa zmianie,
• kopiec nie jest automatycznie przebudowywany – po modyfikacji elementu konieczne jest przebudowanie kopca (O(n)).

Rozwiązania:

1. Wskaźniki – przechowywanie wskaźników do obiektów zamiast kopii;
2. Algorytmy z ponownym wstawianiem – na przykład w algorytmie Dijkstry, po aktualizacji odległości wierzchołek jest ponownie wstawiany do kolejki;
3. 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

1. Brak dostępu do elementów – dostępny jest tylko element top();
2. Brak iteratorów – niemożliwe jest przeglądanie elementów kolejki;
3. Aktualizacja priorytetów – wymaga stosowania obejść (np. wskaźniki);
4. Wydajność – push i pop: O(log n), tworzenie kopca: O(n), brak optymalnej lokalności w cache dla dużych struktur.

Alternatywy i rozszerzenia

1. std::set – umożliwia aktualizację (usunięcie i ponowne wstawienie), ale operacje w czasie O(log n) i wyższe zużycie pamięci;
2. boost::heap – pairing_heap: obsługuje update oraz decrease_key w czasie O(log n);
3. __gnu_pbds::priority_queue (GCC) –

__gnu_pbds::priority_queue<T, Compare, Tag> pq;
auto it = pq.push(x);
pq.modify(it, new_x); // Aktualizacja

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.