Stl Priority Queue For Structure Or Class

Priority Queue:

Priority queue is an abstract data type, It is a type of queue in which each element has a priority assigned to it. The priority of the element determines the order in which elements are removed from the priority queue. In the priority queue, all the elements are arranged either in ascending order or descending order.

Priority Queue Properties:

  • In the priority queue, every element has priority assigned to it.
  • The element with highest priority first.
  • If two elements are having the same priority then they are served according to their order in the queue.

Basically priority queue designed in such a way that the greatest or smallest element is placed on the top of the queue. however,
In STL, the top element of the priority queue is always the greater element. Also, we can change it to the smallest element of the queue.
By default, priority queue is a max-heap.
So basically in this article we’ll study how we can use priority queue for data types like class and structure.
For example, we have a structure named student which consists of two variables Rollno and Address and we want to store them in priority queue.

   struct student{
   int Rollno;
   float Address;
   }

The below example of priority queue gives us error as priority_queue doesn’t know in what order (max or min) we need to arrange the objects.

Defining priority queue:

 priority_queue pq;

To rectify the above error we’ll use operator overloading to define the priority, so that priority_queue can decide how to store the objects.

Now, what is operator overloading?

Operators are used to work for user-defined classes i.e. C++ has the ability to provide the operators with a special meaning for a data type, this is known as operator overloading. Operator overloading is a compile time polymorphism in OOPs.

For example:

int a;
float b,add;
add = a + b;

In the above example, “a” and “b” are the variables of int and float data type, which are built in data types. Hence the addition operator “+” can easily add the contents of variable “a” and “b”. This is because the addition operator “+” is predefined to add variables of pre-defined data types only.

Implementation of priority_queue using structure:

#include <iostream>
#include <queue>
using namespace std;
#define ROW 5
#define COL 2

struct student {

	int rollno;

	float marks;

	student(int rollno, float marks)
		: rollno(rollno), marks(marks)
	{
	}
};

struct Comparemarks {
	bool operator()(student const& s1, student const& s2)
	{
		return s1.marks < s2.marks;
	}
};

int main()
{
	priority_queue<student, vector<student>, Comparemarks> Q;

	float arr[ROW][COL] = { { 3, 5.5 }, { 2, 5 },
					{ 20, 6 }, { 33, 6.5 }, { 23, 5.1 } };

	for (int i = 0; i < ROW; ++i) {

		Q.push(student(arr[i][0], arr[i][1]));

	}

	while (!Q.empty()) {
		student p = Q.top();
		Q.pop();
		cout << p.rollno << " " << p.marks << "\n";
	}
	return 0;
}

Implementation of Priority_queue using class:

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

#define ROW 5
#define COL 2

class student {

public:
	int rollno;

	float marks;

	student(int rollno, float marks)
		: rollno(rollno), marks(marks)
	{
	}
};

bool operator<(const student& s1, const student& s2)
{

	return s1.marks < s2.marks;
}

int main()
{

	priority_queue<student> Q;

		float arr[ROW][COL] = { { 3, 5.5 }, { 2, 5 },
					{ 20, 6 }, { 33, 6.5 }, { 23, 5.1 } };

	for (int i = 0; i < ROW; ++i) {

		Q.push(student(arr[i][0], arr[i][1]));

	}

	while (!Q.empty()) {

		student p = Q.top();

		Q.pop();

		cout << p.rollno << " " << p.marks << "\n";
	}
	return 0;
}

This article tried to discuss Stl Priority Queue For Structure Or Class. Hope this blog helps you understand the concept. To practice problems feel free to check MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *