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?
In Java, Priority Queue, by default implement min Priority Queue, If we need to change the order of Priority Queue from min to max Priority Queue, then we use some methods as follows: Using default Comparator Collections. reverseOrder() Using custom Comparator.
Priority queue is an abstract data type for storing a collection of prioritized elements that supports insertion and deletion of an element based upon their priorities, that is, the element with first priority can be removed at any time.
It supports only those elements that are comparable. Hence, a priority queue in the data structure arranges the elements in either ascending or descending order. You can think of a priority queue as several patients waiting in line at a hospital.
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.
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;
You should create your own domain class rather than using pair<int, int>
here, as far as I can see. Then you can overload >
as you like.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With