How do you keep a priority queue of pairs that's ordered by the second element?

Question

Suppose we have a priority queue such as:

priority_queue<pair<int, int> > pQ;

and we want pQ to be ordered so that the pair with the smallest second element is always first. Is there a simple way to accomplish this using C++11? It would be ideal if I had an elegant solution such as one that uses lambda functions. Is this possible?

juanchopanza · Accepted Answer · 2014-10-08 20:57:44Z

4

You need to instantiate it with a custom comparison function, for example (namespace std assumed):

auto cmp = [](const pair<int, int>& lhs, const pair<int, int>& rhs) { return lhs.second < rhs.second; }; priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pQ(cmp);

edited Oct 8, 2014 at 20:57

answered Oct 8, 2014 at 20:50

juanchopanza

228k35 gold badges421 silver badges493 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Bob Jonas Over a year ago

Can you describe how to use this?

juanchopanza Over a year ago

@BobJonas Ehm, just use it?

Bob Jonas Over a year ago

How do I push things onto the queue?

juanchopanza Over a year ago

@BobJonas Just like you normally would.

Bob Jonas Over a year ago

Oh. I was using the un-edited version before and it wasn't compiling. Thanks for this!

eerorika · Accepted Answer · 2014-10-08 20:50:31Z

Yes, it's possible. std::priority_queue has a templated Compare functor that is used for sorting. You can use a lambda as the functor in c++11.

Rithik Singh · Accepted Answer · 2019-08-07 12:38:22Z

auto cmp=[](pair a,pair b){return a.second>b.second;}; priority_queue,vector>,decltype(cmp)> pq(cmp);

this is min heap of pairs by the second element in the pair.

Collectives™ on Stack Overflow

How do you keep a priority queue of pairs that's ordered by the second element?

3 Answers 3

5 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Related