Priority queue in C++ STL

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.

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

void print(priority_queue<int> q)
{
	priority_queue<int> g = q;
	while (!g.empty()) {
		cout << '\t' << g.top();
		g.pop();
	}
	cout << '\n';
}

// Driver Code
int main()
{
	priority_queue<int> q;
	q.push(10);
	q.push(30);
	q.push(20);
	q.push(5);
	q.push(1);

	cout << "The priority queue q is : ";
	print(q);

	cout << "\nq.size() : " << q.size();
	cout << "\nq.top() : " << q.top();

	cout << "\nq.pop() : ";
	q.pop();
	print(q);

	return 0;
}

By default C++ creates a max heap for the priority queue.

Now, How to create a min-heap for the priority queue?

For the min-heap we’ll pass another parameter to make a min-heap.

Syntax:
priority_queue <int, vector<int>, greater<int>> g = q;

Min heap Code:

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

void print(priority_queue<int, vector<int>, greater<int> > q)
{
	priority_queue<int, vector<int>, greater<int> > g = q;
	while (!g.empty()) {
		cout << '\t' << g.top();
		g.pop();
	}
	cout << '\n';
}

int main()
{
	priority_queue<int, vector<int>, greater<int> > q;
	q.push(100);
	q.push(300);
	q.push(200);
	q.push(5);
	q.push(1);

	cout << "The priority queue q is : ";
	print(q);

	cout << "\nq.size() : " << q.size();
	cout << "\nq.top() : " << q.top();

	cout << "\nq.pop() : ";
	q.pop();
	print(q);

	return 0;
}

using namespace std;

void print(priority_queue<int> q)
{
	priority_queue<int> g = q;
	while (!g.empty()) {
		cout << '\t' << g.top();
		g.pop();
	}
	cout << '\n';
}

// Driver Code
int main()
{
	priority_queue<int> q;
	q.push(10);
	q.push(30);
	q.push(20);
	q.push(5);
	q.push(1);

	cout << "The priority queue q is : ";
	print(q);

	cout << "\nq.size() : " << q.size();
	cout << "\nq.top() : " << q.top();

	cout << "\nq.pop() : ";
	q.pop();
	print(q);

	return 0;
}

This article tried to discuss the Priority queue in C++ STL. Hope this blog helps you understand the implementation. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes

Leave a Reply

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