On what data structure is a priority queue based?

The priority queue in the C++ standard library (std::priority_queue) is by default based on a heap data structure. Specifically, it uses a max-heap by default, where the largest element is always at the root.

This allows for efficient execution of two key priority queue operations:

• Extracting the element with the highest priority (usually top() + pop()): O(log N)
• Adding a new element (push()): O(log N)

Under the hood, std::priority_queue uses an arbitrary container supporting random access (by default std::vector) to store elements and maintains the heap property by calling global functions std::make_heap, std::push_heap, and std::pop_heap.

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

int main() {
    // Creating a priority_queue using a vector as the underlying container
    std::priority_queue<int, std::vector<int>, std::less<int>> pq; // less<int> for max-heap

    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "Top element: " << pq.top() << std::endl; // 30

    pq.pop(); // Remove 30

    std::cout << "Top element after pop: " << pq.top() << std::endl; // 20

    return 0;
}