Priority Queue in C++ Programming

Internally, the priority_queue in C++ is implemented using a binary heap:

• Max Heap (default): The largest element is at the root.
• Min Heap: The smallest element is at the root (by using greater comparator).

A binary heap is a complete binary tree that follows the heap property:

• Max Heap: parent ≥ children
• Min Heap: parent ≤ children

Declaration and Initialization Examples – Priority Queue in C++

In C++, priority_queue is a part of the Standard Template Library (STL), and you can initialize it in different ways depending on your use case.

Let’s explore the three most commonly used ways:

1. Default Declaration (Max Heap)

By default, the priority_queue in C++ works as a Max Heap, where the largest element has the highest priority.

Code:

#include<iostream>
#include<queue>
using namespace std;

int main() {
    priority_queue maxHeap;

    maxHeap.push(50);
    maxHeap.push(10);
    maxHeap.push(30);

    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }

    return 0;
}

Output:

50 30 10

Explanation:

• The largest element 50 is placed at the top.
• On each pop(), the next highest element is displayed.
• This is the default behavior, max heap.

2. Min Heap using greater<> Comparator

To convert the default max heap into a min heap, we need to pass three arguments to priority_queue:

priority_queue<datatype, vector<datatype>, greater<datatype>> minHeap;

Code:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main() {
    priority_queue<int, vector, greater> minHeap;

    minHeap.push(50);
    minHeap.push(10);
    minHeap.push(30);

    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }

    return 0;
}

Output:

10 30 50

Explanation:

• The smallest element (10) is given highest priority.
• Min heap is useful in algorithms like Dijkstra’s shortest path, A algorithm*, etc