Priority Queue of Pairs In C++ with Ordering

Malay Gain
Last Updated: May 13, 2022

Introduction

Priority queue is a special kind of queue where its elements pop out from it following an order based on its priority. If greater elements are popped out earlier to the lesser elements, the priority queue is called max-heap. If lesser elements are popped out prior to the greater elements, the priority queue is called min-heap.

 

Priority queue can contain data of abstract data types as well as user-defined data types such as structure, pair, objects.

 

Here we will be discussing on priority queue that contains pair of integers and its ordering based on the first element and the second element.

 

Ordering by the first element of pair

Ordering by the first element means we need to implement the priority queue such that the ordering of its pair elements depends on the value of the first element of a pair. So, for max-heap implementation, pairs with a greater first value will get higher priority than pairs with the lesser first value. For min-heap implementation, pairs with lesser first value will get higher priority than pairs with the greater first value.

 

Example

 

By default, the C++ STL library provides the implementation of max-heap for the priority queue. So, the default ordering of pairs in a priority queue is also based on the first element.

 

Note: Please try to solve the problem first and then see the below solution approach.

 

 Code

 

// ordering by the first element of pairs in the priority queue(max-heap)

#include <bits/stdc++.h>
using namespace std;

//  print the data of
// the priority queue ordered by first
void print_pq( priority_queue<pair<intint> > pq)
{
// printing and popping out the elements
// until the priority queue
// is not empty
while (!pq.empty()) 
{
cout << pq.top().first<<" "<< pq.top().second<< endl;
pq.pop();
}
cout << endl;
}

// driver Code
int main()
{
priority_queue<pair<intint> > p;

// inserting of elements
p.push(make_pair(19));
p.push(make_pair(84));
p.push(make_pair(45));
p.push(make_pair(33));
p.push(make_pair(27));
print_pq(p);
return 0;
}

 

Output

 

8 4

4 5

3 3

2 7

1 9

 

Ordering by the second element of pair

Ordering by the second element means we need to implement the priority queue. The ordering of its pair elements depends on the value of the second element of a pair. So, for max-heap implementation, pairs with greater second values will get higher priority than pairs with the lesser second value. For min-heap implementation, pairs with lesser second values will get higher priority than pairs with the greater second values.

 

Example

 

Here we need to use the concept of operator overloading for getting such ordering using the priority queue implementation provided by STL  i.e.

 

priority_queue <type, vector<type>, ComparisonType > pq

 

Here ComparisonType is either function or functor(function object) with return value of boolean type. We will implement this functor in such a way that ordering will be based on the second element of the pairs.

 

Go through the code for better understanding.

 

Note: Please try to solve the problem first and then see the below solution approach.

 

Code

 

// ordering by the first element of pairs in the priority queue(max-heap)

#include <bits/stdc++.h>
using namespace std;

//  print the data of
// the priority queue ordered by first
void print_pq( priority_queue<pair<int, int> > pq)
{
	// printing and popping out the elements
	// until the priority queue
	// is not empty
	while (!pq.empty()) {
		cout << pq.top().first<<" "<< pq.top().second<< endl;
		pq.pop();
	}
	cout << endl;
}

// driver Code
int main()
{
	priority_queue<pair<int, int> > p;
	// inserting of elements
	p.push(make_pair(1, 9));
	p.push(make_pair(8, 4));
	p.push(make_pair(4, 5));
	p.push(make_pair(3, 3));
	p.push(make_pair(2, 7));
	print_pq(p);
	return 0;
}

 

Output

 

1 9

2 7

4 5

8 4

3 3

 

FAQs

1). What is a priority queue?

It is a special kind of queue where each element has its own priority and elements are served (poped out) according to this priority.

 

2). How to implement min-heap using C++ STL library?

In C++, STL library priority_queue is by default made max-heap. To use priority_queue as min-heap, we need to add two extra arguments as shown below.

 

priority_queue<type, vector<type>, greater<type> > pq;

 

Key Takeaways

This article covered how to make ordering a priority queue of pairs by its first and second elements. A good grasp of the priority queue can be a huge plus point in a coding interview.

 

Check out the CodeStudio library for getting a better hold of the data structures and algorithms.

 

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in CodeStudio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

 

Happy learning!

 

 

Was this article helpful ?
0 upvotes