CODEWITHSUNDEEP
c++priority-queuestd-pair
cazaimi
cazaimi

Reputation: 193

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

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.

Upvotes: 4

Views: 2840

Answers (1)

Benjamin Lindley
Benjamin Lindley

Reputation: 103693

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.

Upvotes: 6

Related Questions