Wat is de datastructuur priority_queue?

priority_queue — een containeradapter uit de C++ standaardbibliotheek die functionaliteit voor een prioriteitswachtrij biedt. De elementen worden in volgorde van prioriteit verwijderd (standaard heeft het grootste element de hoogste prioriteit). Het is in wezen een omhulsel rond een andere container (standaard std::vector) die heap-algoritmen (std::make_heap, std::push_heap, std::pop_heap) gebruikt om de heap-structuur binnen de basiscontainer te behouden.

Belangrijke kenmerken:

• Prioriteit: Elementen worden volgens hun prioriteit verwijderd. Standaard wordt std::less gebruikt om de prioriteit te bepalen, wat betekent dat het grootste element de hoogste prioriteit heeft (max-heap). Je kunt de volgorde aanpassen door een andere comparator te gebruiken, bijvoorbeeld std::greater voor een min-heap.
• Adapter: priority_queue is geen zelfstandige container, maar past een andere basiscontainer aan (meestal std::vector, maar het kan ook std::deque zijn), en biedt een interface voor een prioriteitswachtrij.
• Heap: Intern geïmplementeerd met behulp van een heap, wat logaritmische complexiteit garandeert voor insertie- en verwijderingsoperaties.
• Ongeordende toegang: Biedt geen willekeurige toegang tot elementen. Alleen de operaties push, pop (verwijder het element met de hoogste prioriteit) en top (bekijk het element met de hoogste prioriteit) zijn beschikbaar.

Belangrijkste operaties:

Operatie	Beschrijving	Gemiddelde / slechtste geval complexiteit
push	Voegt een element toe met een gegeven prioriteit.	O(log N)
pop	Verwijdert het element met de hoogste prioriteit.	O(log N)
top	Geeft een constante referentie op het element met de hoogste prioriteit.	O(1)
empty	Controleert of de wachtrij leeg is.	O(1)
size	Krijgt het aantal elementen in de wachtrij.	O(1)

Voorbeeld:

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

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

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

    // Min-heap (met 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 << "Elementen van min-heap (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}