How is priority queue work?

general
, , ,
1

I want to know, how is priority queue work for pairs?

priority_queue< pair <int,int> >q; //here priority queue stores number in pairs.

Like how numbers are prioritized in the queue in case of pairs?

Can we choose whether it should be according to first element or second?

I hope you understand my question. pls, help…

2

its simple, generally for two pairs (a,b) and (c,d); (a,b) has higher priority than (c,d) if a>c or a==c and b>d.

And of course you can provide suitable comparing function and change the way it is prioritized…

3

Check this link.
Hope I helped :slight_smile:

4

In case of pairs, priority queue always works according to first element.
Now, if you want to change this, here’s what you can do:

1.Declare your priority queue like this:

priority_queue<pair<int,int>,vector<pair<int,int> >,cmp>pq;

Here, the vector of pair is the container class of your priority_queue and cmp is the comparator class.

2.Now to write the cmp class.

class cmp
{
public:
    bool operator()(pii a,pii b)
    {
        //conditions of compare
    }
};
2 Likes
5

sure…(explaining your case)

first create a comparator class

class comp{

public:

operator() (pair<int,int>a,pair<int, int> b){

if(a.first==b.first)return a.second > b.second;

else return a.first > b.first;
}
}

operator () is standard in c++ :wink:

then declare priority queue as follow-

priority_queue<pair<int,int>,vector< pair<int,int> >,comp > p;

note that it takes 3 argument-1st one is obvious, 2nd one is the container class(u may call it as underlying data structure), 3rd one is compare class…

consider another case-

suppose a pair denotes a point in 2-d plane, you want to give priority to that point which is more closer to the origin. the u can modify your compare class as following-

class comp{

public:

operator() (pair<int,int>a,pair<int, int> b){

return a.first^2 + a.second^2 < b.first^2+ b.second^2

}
}

also instead of using compare class u can use lambda(if you are familiar)…

auto cmp = [](int a, int b) { return a>b;};

std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);

hope it helps…