Hi everyone

In this tutorial we will talk about Priority Queue

So, What is Priority Queue actually?

Priority Queue is a special type of queue where each element has a priority associated with it. Elements with higher priority are served before elements with lower priority, regardless of their insertion order.

STL Priority Queue also works the same way

By default, STL Priority Queue is a Max Heap, which means the largest element is always at the top.

STL Priority Queue container’s underlying data structure is vector (with heap operations applied on it)

Header File Inclusion for priority_queue

#include <queue>

Declaration


#include <queue>

priority_queue <int> pq;

Insertion

push() method

With push() method we insert data into a priority queue. After every insertion, the heap property is automatically maintained, so the largest element always sits at the top.


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

After Insertion priority queue (top to bottom) will look like this —

emplace() method

We can also insert values to priority queue with emplace() method —


pq.emplace(100);
pq.emplace(5);

After Insertion priority queue will look like this —

100

Accessing the element

top() method
top() method of priority queue returns the highest priority element (the largest element by default)


// this will output the top element from priority queue
cout << pq.top() << endl;

Output will be – 100

Deletion

pop() method

Priority queue’s pop() method removes the top element from the priority queue


// removing element 100, now current top 75
pq.pop();

// removing element 75, now current top 50
pq.pop();

// removing element 50, now current top 30
pq.pop();

After Deletion priority queue will look like this —

Min Heap Priority Queue

By default, priority queue works as a Max Heap. But sometimes we need the smallest element on top instead of the largest one. For that, we can declare a Min Heap priority queue —


priority_queue <int, vector<int>, greater<int>> minPq;

minPq.push(20);
minPq.push(50);
minPq.push(10);
minPq.push(75);
minPq.push(30);

After Insertion min heap priority queue will look like this —


// this will output the top element from min heap priority queue
cout << minPq.top() << endl;

Output will be – 10

Priority Queue with Pair

Sometimes a single value is not enough — we need to store two related values together. For that, we can use a priority queue of pairs. By default, a priority queue of pairs orders elements according to the first element of the pair. If the first elements are equal, then the second element is used as the tie-breaker.

Ordered by the first element

Descending (default — Max Heap)


priority_queue < pair<int, int> > firstOrdered;

Or, to make the code cleaner, we can use a typedef —


typedef pair<int, int> couple;
priority_queue < couple > firstOrdered;

Let’s push some pairs into it —


firstOrdered.push(make_pair(10, 200));
firstOrdered.push(make_pair(30, 100));
firstOrdered.push(make_pair(20, 400));
firstOrdered.push(make_pair(30, 50));

The pair with the largest first element will sit at the top —

30	100
30	50
20	400
10	200

Ascending (Min Heap)

priority_queue < pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > firstOrdered;

Or, with a typedef —


typedef pair<int, int> couple;
priority_queue < couple, vector<couple>, greater<couple> > firstOrdered;

After pushing the same pairs, the pair with the smallest first element will sit at the top —

10	200
20	400
30	50
30	100

Ordered by the second element

To order pairs based on the second element, we need to write our own comparator using a struct.

Descending (Max Heap on second element)


typedef pair<int, int> couple;

struct compare
{
    bool operator()(couple& a, couple& b)
    {
        return a.second < b.second;
    }
};

priority_queue < couple, vector<couple>, compare > priceList;

while (test--)
{
    cin >> id >> price;
    priceList.push(make_pair(id, price));
}

while (!priceList.empty())
{
    couple hand = priceList.top();
    priceList.pop();
    cout << hand.first << " " << hand.second << endl;
}

The pair with the largest second element will be served first.

Ascending (Min Heap on second element)

We just need to flip the comparison sign in the comparator —


typedef pair<int, int> couple;

struct compare
{
    bool operator()(couple& a, couple& b)
    {
        return a.second > b.second;
    }
};

priority_queue < couple, vector<couple>, compare > priceList;

while (test--)
{
    cin >> id >> price;
    priceList.push(make_pair(id, price));
}

while (!priceList.empty())
{
    couple hand = priceList.top();
    priceList.pop();
    cout << hand.first << " " << hand.second << endl;
}

Now the pair with the smallest second element will be served first.

💡 Quick tip on the comparator logic — In a priority queue, the comparator works the opposite way of how you might expect. Returning a.second < b.second gives you a Max Heap (largest on top), and returning a.second > b.second gives you a Min Heap (smallest on top).

Priority Queue with Nested Pair

Sometimes we need to store three related values together — for example, the source, destination, and weight of an edge in a graph. For that, we can use a nested pair, where one element of the pair is itself another pair.

A common pattern is to keep the weight as the first element (so the priority queue orders edges by weight), and store the source and destination together as the inner pair.

Ordered according to the first element

Descending (default — Max Heap)


typedef pair< int, pair<int, int> > nestedCouple;

priority_queue < nestedCouple > weightedList;

while (test--)
{
    cin >> source >> destination >> weight;
    weightedList.push(make_pair(weight, make_pair(source, destination)));
}

while (!weightedList.empty())
{
    nestedCouple hand = weightedList.top();
    weightedList.pop();
    cout << hand.second.first << " " << hand.second.second << " " << hand.first << endl;
}

The edge with the largest weight will come out first.

Ascending (Min Heap)


typedef pair< int, pair<int, int> > nestedCouple;

priority_queue < nestedCouple, vector<nestedCouple>, greater<nestedCouple> > weightedList;

while (test--)
{
    cin >> source >> destination >> weight;
    weightedList.push(make_pair(weight, make_pair(source, destination)));
}

while (!weightedList.empty())
{
    nestedCouple hand = weightedList.top();
    weightedList.pop();
    cout << hand.second.first << " " << hand.second.second << " " << hand.first << endl;
}

The edge with the smallest weight will come out first. This pattern is exactly what we use in Dijkstra’s and Prim’s algorithms.

💡 Note on accessing nested pair values — Since the inner pair sits inside .second, we need to write hand.second.first and hand.second.second to access the source and destination respectively, while the weight stays at hand.first.

Swapping

swap() method

There is a scenario that, someone need to swap values between two priority queue and if he is thinking about creating

auxiliary priority queues. There is a good news for him. We don’t need to create auxiliary priority queues if we are using STL priority queue.

STL priority queue has a method named swap(), which swaps values of two priority queue data structures —


priority_queue <int> listOne;
listOne.push(128);
listOne.push(64);
listOne.push(32);

After Insertion listOne will look like this —

128


priority_queue <int> listTwo;
listTwo.push(1);
listTwo.push(2);
listTwo.push(4);

After Insertion listTwo will look like this —

Now, let’s swap the elements of two priority queue —


// swapping values between two priority queues
listOne.swap(listTwo);

After Swapping listOne will look like this —

After Swapping listTwo will look like this —