Mi az a priority_queue adatstruktúra?

priority_queue — egy konténeradapter a C++ standard könyvtárból, amely prioritási sor funkciót nyújt. A elemek a prioritásuk szerint kerülnek kivételre (alapértelmezés szerint a legnagyobb elem a legmagasabb prioritású). Lényegében ez egy másik konténer (alapértelmezés szerint std::vector) fölött működő burkolat, amely heap algoritmusokat (std::make_heap, std::push_heap, std::pop_heap) használ a heap struktúra fenntartására a belső konténerben.

Fő jellemzők:

• Prioritás: Az elemek a prioritásuk szerint kerülnek kivételre. Alapértelmezés szerint a std::less van használatban, ami azt jelenti, hogy a legnagyobb elem a legmagasabb prioritású (max-heap). Más összehasonlítót is meg lehet adni, például std::greater-t a min-heaphez.
• Adapter: A priority_queue nem önálló konténer, hanem egy másik alapkonténert (általában std::vector, de lehet más is, például std::deque) adaptál, és prioritási sor interfészt biztosít.
• Heap: Belsőleg heap-ként van megvalósítva, ami logaritmikus komplexitást biztosít beszúrás és kivétel műveleteknél.
• Nem rendezett hozzáférés: Nem biztosít véletlenszerű hozzáférést az elemekhez. Csak beszúrás (push), a legmagasabb prioritású elem kivétele (pop) és a legmagasabb prioritású elem megtekintése (top) érhető el.

Fő műveletek:

Művelet	Leírás	Átlagos/legrosszabb esetbeli komplexitás
push	Egy elem beszúrása adott prioritással.	O(log N)
pop	A legmagasabb prioritású elem eltávolítása.	O(log N)
top	Állandó referencia visszaadása a legmagasabb prioritású elemre.	O(1)
empty	Ellenőrzi, hogy üres-e a sor.	O(1)
size	A sor elemeinek száma.	O(1)

Használati példa:

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // std::greater számára

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

    std::cout << "Max-heap elemei (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Min-heap (std::greater<int> használatával)
    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 << "Min-heap elemei (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

Olyan algoritmusokban használják, ahol folyamatosan a legmagasabb (vagy legalacsonyabb) prioritású elemet kell kivonni, például Dijkstra, Prim algoritmusokban vagy esemény szimulációkban.