How does a priority queue work in C++?

How does a priority queue work in C++?

A priority queue is an abstract data type where each element has a priority. Elements with higher priority are served before those with lower priority.

Can you show me how to implement one using the STL?

Sure! You can use the std::priority_queue from the Standard Template Library. Here's a simple example:

#include <queue>
#include <vector>
#include <iostream>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(20);
    pq.push(15);

    while (!pq.empty()) {
        std::cout << pq.top() << ' '; // Outputs: 20 15 10
        pq.pop();
    }
    return 0;
}

What if I want to implement a min-heap instead?

You can use a custom comparator. For a min-heap, you can define a priority queue like this:

#include <queue>
#include <vector>
#include <iostream>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(15);

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << ' '; // Outputs: 10 15 20
        minHeap.pop();
    }
    return 0;
}