Logic behind the custom comparator for std::priority_queue

Question

I am trying to write a custom comparator for the following priority queue:

priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;

The first int in the pair is the key, and the second int is the count of the key. I want my priority queue to put the pair with the largest count at the top.

The following is my functor that has fulfilled my need:

class cmp{
public:
   bool operator()(const pair<int,int> a, const pair<int,int> b)const{
        return a.second < b.second;
    }

};

I do not quite understand why this is the correct way to do it. Why the comparator returns a.second < b.second instead of a.second > b.second, since I want to put the pair with the most count at top? And how the priority queue will actually utilize this comparator?

Answer 1

From std::priority_queue's documentation:

Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last.

The same happens with std::make_heap(): providing a comparator that returns a < b – what std::less does – results in this function template building a max-heap, i.e., the element with the highest key is at the top of the heap. If you want to build a min-heap, you have to pass operator> instead of operator< or still, use operator< but flip the operands.

To conclude, both std::priority_queue and the function templates for dealing with binary heaps sort their elements so that the top corresponds to the element with the highest key. How two keys compare to each other is, however, up to you. You can control this by providing a custom comparator.