C++ STL Priority Queue

general
,
1

Hello,

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.

2

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
3

Thanks for your answer. But could you explain this
pair<int,string>,vector<pair<int,string>>,greater<pair<int,string>>

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

4

Thank You.

5

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;

6

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.

7

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.