Čo je dátová štruktúra priority_queue?

priority_queue — adaptér kontajnera zo štandardnej knižnice C++, ktorý poskytuje funkcionalitu fronty s prioritami. Prvky sú vyberané podľa ich priority (predvolene, najväčší prvok má najvyššiu prioritu). V podstate je to obal nad iným kontajnerom (predvolene std::vector), ktorý používa algoritmy haldy (std::make_heap, std::push_heap, std::pop_heap) na udržiavanie štruktúry haldy vo vnútri základného kontajnera.

Kľúčové vlastnosti:

• Priorita: Prvky sú vyberané podľa ich priority. Predvolene sa používa std::less, čo znamená, že najväčší prvok sa považuje za s najvyššou prioritou (max-heap). Môže byť zmenené poradie, poskytnutím iného porovnávača, napr. std::greater pre min-heap.
• Adapter: priority_queue nie je samostatný kontajner, ale adaptér nad iným základným kontajnerom (zvyčajne std::vector, ale môže byť aj iný, napr. std::deque), ktorý poskytuje rozhranie fronty s prioritami.
• Hlava: Interné je implementované pomocou haldy, čo zabezpečuje logaritmickú zložitosť pre operácie vkladania a vyberania.
• Nerovnomerný prístup: Neumožňuje náhodný prístup k prvkom. Sú dostupné iba operácie vkladania (push), odstránenia prvku s najvyššou prioritou (pop) a zobrazenia prvku s najvyššou prioritou (top).

Hlavné operácie:

Operácia	Popis	Zložitosť (priemer/horší prípad)
push	Vloží prvok s danou prioritou.	O(log N)
pop	Odstráni prvok s najvyššou prioritou.	O(log N)
top	Vráti konštantnú referenciu na prvok s najvyššou prioritou.	O(1)
empty	Skontroluje, či je fronta prázdna.	O(1)
size	Získa počet prvkov vo fronte.	O(1)

Príklad použitia:

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // pre std::greater

int main() {
    // Max-heap (predvolené)
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);

    std::cout << "Prvky max-heapu (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Min-heap (použitím std::greater<int>)
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);

    std::cout << "Prvky min-heapu (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

Používa sa v algoritmoch, kde je potrebné neustále vyberať prvok s najvyšším (alebo najnižším) priorítom, napr. Dijkstrův algoritmus, Primov algoritmus alebo v simuláciách udalostí.