Priority Queue of Pairs In C++ with Ordering

Q: Which type of priority queue is predefined in CPP?

The priority queue of pairs ordered by the first element using the max heap approach is predefined in CPP

Introduction

From our school days, we have learned about a data structure called queue, right? So we all know that a queue is a data structure that follows the first in first out (FIFO) principle.

Queues are of four types - linear, circular, dequeue, and priority. As the title suggests, this article deals with priority queues of a particular type.

Priority Queue of Pairs in CPP With Ordering

Before moving on to that, for a quick recap, a priority queue is a data structure in which we can add elements in any order as in a normal queue, but they are popped and printed based on their priority. In other words, the elements are printed or popped in ascending order.

Now, this article deals with priority queue of pairs. So let’s learn what they are first.

Priority Queue of Pairs

Before we move on to the priority queue of pairs, let us first see an example of a priority queue.

Suppose we push the elements 23, 75, 17, 99, and 5 into a priority queue. The priority is determined by the element's weight (or you may also take it to be the value). So, on printing the queue, the output will be 99, 75, 23, 17, 5.

Now, instead of a single element, a pair of elements is pushed into a priority queue of pairs. So, modifying the same example, suppose we push the pairs (23, 10), (75, 19), (17, 74), (99, 18), and (5, 37).

Now, the question arises which element will we consider while prioritizing pop?

The answer to this is in the idea of ordering. Let us see what that is next.

Priority Queues of Pairs With Ordering

We already know that priority queues of pairs are a kind of priority queue, which is a type of queue, but that’s not the end of the story.

Based on which element in the pair of elements will be used for prioritizing, priority queues of pairs are also of two types. The types are:

(i) priority queue of pairs ordered by the first element in the pair

(ii) priority queue of pairs ordered by the second element in the pair

Let’s see what both of them are.

Priority Queue of Pairs Ordered by the First Element (Max Heap)

To understand priority queue of pairs ordered by the first element, let us consider our previous example.

The pairs pushed in the queue were (23, 10), (75, 19), (17, 74), (99, 18), and (5, 37).

If the first element order these pairs, each pair's first number will be considered while prioritizing. So the output on printing the queue above will be (99,18), (75, 19), (23, 10), (17, 74), and (5, 37).

Popping Elements From a Priority Queue Ordered By The First Element (Max Heap)

Now that we have an idea of priority queue of pairs ordered by the first element let’s try to write the CPP code for it. For your convenience, the algorithm and solution are given below but try to write it yourself first.

Algorithm:

Step 1: Define a priority queue that stores a pair of integers.

Step 2: Take the number of pairs and the elements in the queue as input from the user.

Step 3: Store the pair of integers in the priority queue using a loop.

Step 4: Run a loop till the priority queue is empty.

Step 5: Print the element on top of the queue and pop it.

Code:

// Priority Queue Ordered by the First Element (Max heap)
#include<bits/stdc++.h>
using namespace std;

int main()
{
    // Define a priority queue to store the pair of integers
    priority_queue<pair<int,int>> maxHeapByFirstEl;
    int n;
    
    // Take the number of pairs in the queue as input from the user
    cout<<"Enter no. of pairs: ";
    cin>>n;
    
    // Take the elements in the queue as input from the user
    for(int i=0;i<n;i++)
    {
        cout<<"Enter the 1st and 2nd elements of pair "<<(i+1)<<" separated by space: ";
        int a,b;
        cin>>a>>b;
        
        // Pairs are pushed into the queue
        maxHeapByFirstEl.push({a,b});      
    }
    
    cout<<"Output: "<<endl;
    
    // The loop till the queue is empty
    while(!maxHeapByFirstEl.empty())
    {
        // Prints and pops the element in the top of the queue
        pair<int,int> top=maxHeapByFirstEl.top();
        maxHeapByFirstEl.pop();
        cout<<"("<<top.first<<","<<top.second<<")"<<endl;
    }
    return 0;
}

Output:

Note: This is the predefined defined method to pop the elements from a priority queue of pairs, so we do not need to define any additional class. In the subsequent sections, we will see how to define a class for the other cases.

Now that we know what priority queue of pairs ordered by the first element is let’s learn about the other type of priority queue of pairs.

Priority Queue of Pairs Ordered by the Second Element (Max Heap)

With the knowledge of priority queue of pairs ordered by the first element, can you guess what pairs ordered by the second element are?

If you guessed the prioritization is done with respect to the second element in the pair, you are correct! Still, for proper understanding, let’s use our previous example to find the output.

The input given to the queue was (23, 10), (75, 19), (17, 74), (99, 18) and (5, 37).

On ordering by the second element, the output will be (17, 74), (5, 37), (75, 19), (99, 18), (23, 10).

Popping Elements From a Priority Queue Ordered By The Second Element (Max Heap)

Let’s try writing the code for this too! You may take help from the algorithm in case you’re stuck.

Hint: A custom comparator is used for the prioritization comparisons done between the pairs' second element.

Algorithm:

Step 1: Create a class where a custom comparator is made.

Step 2: Define a priority queue that stores a pair of integers.

Step 3: Take the number of pairs and the elements in the queue as input from the user.

Step 4: Store the pair of integers in the priority queue using a loop.

Step 5: Run a loop till the priority queue is empty.

Step 6: Print the element on top of the queue and pop it.

Code:

// Priority Queue Ordered by the Second Element (Max heap)
#include<bits/stdc++.h>
using namespace std;

// Class to create a custom comparator
class Compare
{
public:
    bool operator()(pair<int,int> a, pair<int,int> b)
    {
        return a.second<b.second;
    }
};

int main()
{
    // Priority queue is defined using the custom comparator
    priority_queue<pair<int,int>,vector<pair<int,int>>,Compare> maxHeapBySecondEl;
    int n;
    
    // Taking user inputs
    cout<<"Enter no. of pairs: ";
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cout<<"Enter 1st and 2nd element of pair "<<(i+1)<<" separated by space: ";
        int a,b;
        cin>>a>>b;
        maxHeapBySecondEl.push({a,b});
    }
    
    cout<<"Output:"<<endl;
    
    // The loop while queue is empty
    while(!maxHeapBySecondEl.empty())
    {
        // Prints and pops the element in the top of the queue
        pair<int,int> top=maxHeapBySecondEl.top();
        maxHeapBySecondEl.pop();
        cout<<"("<<top.first<<","<<top.second<<")"<<endl;
    }
    return 0;
}

Output:

You may have noticed that the largest element is prioritized in the above examples. This approach is called max heap or max priority. There is another approach that is opposite to this. Let’s see what it is in the next section.

Min Heap Approach to Priority Queue of Pairs with Ordering

Another way of prioritizing the queues is called min heap or min priority. This method prioritizes the element with the lowest weight (or value). So, considering the same example, our output for ordering by the first element would’ve been (5, 37), (17, 74), (23, 10), (75, 19), and (99, 18).

Now that we know what the min heap approach does let’s write the code for both ordering by the first and second elements. The algorithms have been given for reference, but try it out yourself first.

Min Heap for Ordering by the First Element

Dry Run:

Popping Elements From a Priority Queue Ordered By The First Element (Min Heap)

Algorithm:

Step 1: Define a priority queue that stores a pair of integers using the default comparator “greater<pair<int,int>>” for min heap priority.

Step 2: Take the number of pairs and the elements in the queue as input from the user.

Step 3: Store the pair of integers in the priority queue using a loop.

Step 4: Run a loop till the priority queue is empty.

Step 5: Print the element on top of the queue and pop it.

Code:

// Priority Queue Ordered by the First Element (Min heap)
#include<bits/stdc++.h>
using namespace std;

int main()
{
    // Priority queue is defined using the “greater<pair<int,int>>” default comparator
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> minHeapByFirstEl;
    int n;
    
    // Taking user inputs
    cout<<"Enter no. of pairs: ";
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cout<<"Enter 1st and 2nd element of pair "<<(i+1)<<" separated by space: ";
        int a,b;
        cin>>a>>b;
        minHeapByFirstEl.push({a,b});
    }
    
    cout<<"Output:"<<endl;
    
    // The loop while queue is empty
    while(!minHeapByFirstEl.empty())
    {
        // Prints and pops the element in the top of the queue
        pair<int,int> top=minHeapByFirstEl.top();
        minHeapByFirstEl.pop();
        cout<<"("<<top.first<<","<<top.second<<")"<<endl;
    }
    return 0;
}

Output:

Min Heap for Ordering by the Second Element

Dry Run:

Popping Elements From a Priority Queue Ordered By The Second Element (Min Heap)

Algorithm:

Step 1: Create a class where a custom comparator is made to compare the second elements in the pairs.

Step 2: Define a priority queue that stores a pair of integers using the default comparator “greater<pair<int,int>>”.

Step 3: Take the number of pairs and the elements in the queue as input from the user.

Step 4: Store the pair of integers in the priority queue using a loop.

Step 5: Run a loop till the priority queue is empty.

Step 6: Print the element on top of the queue and pop it.

Code:

// Priority Queue Ordered by the Second Element (Min heap)
#include<bits/stdc++.h>
using namespace std;

class Compare
{
public:
    bool operator()(pair<int,int> a, pair<int,int> b)
    {
        return a.second>b.second;
    }
};

int main()
{
    // Priority queue is defined using the custom comparator
    priority_queue<pair<int,int>,vector<pair<int,int>>,Compare> minHeapBySecondEl;
    int n;
    
    // Taking user inputs
    cout<<"Enter no. of pairs: ";
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cout<<"Enter 1st and 2nd element of pair "<<(i+1)<<" separated by space: ";
        int a,b;
        cin>>a>>b;
        minHeapBySecondEl.push({a,b});
    }
    
    cout<<"Output:"<<endl;
    
    // The loop while queue is empty
    while(!minHeapBySecondEl.empty())
    {
        // Prints and pops the element in the top of the queue
        pair<int,int> top=minHeapBySecondEl.top();
        minHeapBySecondEl.pop();
        cout<<"("<<top.first<<","<<top.second<<")"<<endl;
    }
    return 0;
}

Output:

Now we have a thorough understanding of priority queue of pairs with ordering. You may revisit this article any number of times for revision.

You can also compile this code with the help of Online C++ Compiler

Frequently Asked Questions

What is a queue?

A queue is a data structure that follows the FIFO mode of operation. This means that the first element added is the first one to be popped. It is also termed “open on both ends” since the operations occur on both ends of the data structure.

What are the different types of queues?

The different types of queues are linear, circular, dequeue, and priority.

What is a priority queue?

A priority queue is a data structure where we can add elements in any order as in a normal queue, but they are popped and printed based on their priority (max heap or min heap).

What is a priority queue of pairs?

A priority queue of pairs is a data structure in which a pair of elements is pushed into the queue, but the elements are popped based on their priority(max heap or min heap).

What are the different types of priority queues of pairs?

The different types of priority queues of pairs are:

(i) Priority queue of pairs ordered by the first element

(ii) Priority queue of pairs ordered by the second element

Which type of priority queue is predefined in CPP?

Priority queue of pairs ordered by the first element using the max heap approach is predefined in CPP.

Conclusion

By the end of this article, we have a thorough understanding of priority queue of pairs with ordering. We learned what a priority queue is and also its different types. We also implemented our knowledge by writing the code for priority queues in CPP. For further reading, you may refer to other blogs on Implementation of Heap, Minheap & Maxheap in Data Structures, Application of Priority Queue, Priority Queue using Java, and, Implement min heap in C++.