Create priority_queue with pair such that sorting is "<" for first element and ">" for second element when 1st elements are equal

Question

I have a basic doubt, in that I am trying to figure out the versatility of priority_queue STL in C++.

I know that priority queue by default is actually a max_heap. I also am aware that it can be modified in the following way to create a min_heap:

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

What I aim to achieve, is that I want to create a priority_queue <pair <int,int> pq, such that heap is a max_heap for the first element in the pair, and it is a min_heap for the second element in the pair. For example, on inserting the following pairs:

(2,4) (1,5) (1,6)

The output when elements are displayed is as follows:

(2,4) (1,5) (1,6)

By default, the output would have been:

(2,4) (1,6) (1,5)

Is it possible? If yes, then how?

Thank you in advance.

I would recommend that you keep the minheap and maxheap separate, and merely use your "pair" convention as a display artifact. — Kenny Ostrom
– Kenny Ostrom, Commented Oct 14, 2017 at 23:45
@KennyOstrom I suspect there aren't actually two heaps, but rather one heap with a secondary ordering property which applies when there are ties on the first ordering property. The wording of the question is unclear. — pjs
– pjs, Commented Oct 14, 2017 at 23:48
That ... can't be possible, can it? If the first elements form a max heap, then the second elements will NOT form a min heap if they are actually paired, except by pure luck. Do (1,1) (2,2) (3,3) — Kenny Ostrom
– Kenny Ostrom, Commented Oct 14, 2017 at 23:50
@KennyOstrom: Yes, it's not possible to form a max-heap for the first element, which is simultaneously a min-heap for the second element. And based on his desired output, I don't think he's asking for that. He's basically asking for a max-heap based on the first element. But in the case where the first elements are equal, the order is decided by the second element, but inversely to the way the order is decided for the first element. — Benjamin Lindley
– Benjamin Lindley, Commented Oct 14, 2017 at 23:56
So basically "how do you write a custom comparitor" then. cool. Yes, c++ does not limit you to only std::greater and std::lesser. Or you could just use them if you define operator< or operator> on the type in question. — Kenny Ostrom
– Kenny Ostrom, Commented Oct 15, 2017 at 0:05

Benjamin Lindley · Accepted Answer · 2017-10-14 23:50:55Z

You can write a custom comparison that compares the first element with operator<, and the second element with operator>.

struct less_then_greater { template<typename T, typename U> bool operator()(T const& lhs, U const& rhs) const { if (lhs.first < rhs.first) return true; if (rhs.first < lhs.first) return false; return lhs.second > lhs.second; } }; std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, less_then_greater > pq;

Note that this isn't creating a min-heap for one, and a max-heap for the other. But based on the output you describe, I don't think that's what you were really asking for.

I agree that min heap for one and max heap for other is not the most accurate way of putting it, but this does it.

Collectives™ on Stack Overflow

Create priority_queue with pair such that sorting is "<" for first element and ">" for second element when 1st elements are equal

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related