C++ STL Priority Queue


I wanted to implement a priority queue using C++ STL priority_queue.

I wanted to store a node in that priority queue. The structure of that node will be as

struct node{
int name;
int val;

The Priority queue should be sorted (or elements should be entered) according to the val variable inside that node.

Kindly help me out how to do this.

Thank You.

Use std::pair for storing name and val instead of using struct node by using this you need not define the ‘<’ or ‘>’ operator for node.
If you want the pair with the smallest value of val, you need a min priority queue or priority queue in the opposite case.

How to use std::priority_queue in this case ?

priority_queue< pair< int, string > , vector< pair< int, string> >, greater< pair< int, string > > > pq;
// assuming name is of type std::string

Pushing an element in pq :

int value;
string name;
cin >> value >> name;
pq.push(make_pair(value, name));

Extracting the minimum value and the name corresponding to that value :

pair< int, string > p = pq.top();
cout << "Minimum value is : " << p.first;
cout << "Name corresponding to " << p.first << " is " << p.second; 

For more information about std::priority_queue refer this.

1 Like

Thanks for your answer. But could you explain this

I am a beginner in C++. Help me in this. This is the min. Heap implementation but What If I needed the Max. Heap.

Thank You.

For now u can consider min heap implem. as syntax for pq with min heap,
Basically we are passing container type,comparision function as a parameter to a pq stl.

For Max Heap, priority_queue <pair<int,int>> pq;

priority_queue<pair<long long int,long long int>,vector<pair<long long int,long long int>>,less<pair<long long int,long long int>>> pq;

if I am changing the greater to less than it is working as the Max. Heap.

yesss ! but u don’t need to use “less” explicitly… as by default, syntax will implement max heap for the first element of pair.

priority_queue< pair<int,int> > pq ; will work same.