Priority queue of pairs in reverse order

c++ priority-queue
bqui56 picture bqui56 · May 26, 2012 · Viewed 16.7k times · Source

I'm wanting to do something like this:

priority_queue< pair<int, int>, vector<int>, greater<int> > Q;

This works fine if the type I'm comparing is int, i.e.:

priority_queue< int, vector<int>, greater<int> > Q;

however, obviously with the pair<int, int>, there is no way of comparing the pairs in the queue with the standard >. I was wondering what I should do? How would I implement an overloaded > or is there another way I can create a priority queue of pairs with the smallest pair.second being at the top of the queue?

Answer

Peter Alexander picture Peter Alexander · May 26, 2012

Have you tried this?

typedef pair<int, int> P;
priority_queue< P, vector<P>, greater<P> > Q;

This will give the reverse ordering of the normal operator< for pair<int, int>, which will start with the smallest first tie-broken with smallest second.

If you want to sort by smallest second first and first second (!) then you'll need a new sorting functor:

struct Order
{
    bool operator()(P const& a, P const& b) const
    {
        return a.second < b.second || a.second == b.second && a.first < b.first;
    }
}

Then use:

priority_queue< P, vector<P>, Order > Q;

Related questions

declaring a priority_queue in c++ with a custom comparator

I'm trying to declare a priority_queue of nodes, using bool Compare(Node a, Node b) as the comparator function (which is outside the node class). What I currently have is: priority_queue<Node, vector<Node>, Compare&…

Read More
How can I create Min stl priority_queue?

The default stl priority queue is a Max one (Top function returns the largest element). Say, for simplicity, that it is a priority queue of int values.

Read More
How to remove element not at top from priority_queue?

In my program I need to delete an element from a priority queue that is not at the top. Can that be done? If not, please suggest a way to do so except creating your own heap.

Read More