3

A std::priority_queue uses a std::vector as the default container (Reference this). For sorting on the basis of the first element in a std::vector<pair<int, int>>, we need to define our own comparison function (Reference this). This is what I understand.

Now, the following code returns the k most frequent elements in a non-empty array, in O(NlogK):

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        if(nums.empty())
            return vector<int>();

        unordered_map< int, int > hashMap;
        for(int i=0; i<nums.size(); i++)
            hashMap[nums[i]]++;

        priority_queue< pair< int, int >> pq;
        vector< int > result;
        unordered_map< int, int >::iterator it=hashMap.begin();

        for(it=hashMap.begin(); it!=hashMap.end(); it++) {
            //the first one is frequency and the second one is the value
            pq.push(make_pair(it->second, it->first));

            //the peculiar implementation below is because we the code to be O(NlogK)
            if(pq.size()>(hashMap.size()-k)) {
                result.push_back(pq.top().second);
                pq.pop();
            }
        }

        return result;
    }
};

This code works correctly and gets accepted by the judge - but how? The std::priority_queue, using a std::vector<pair<int, int>> as its underlying container must contain a custom comparison function so that it sorts correctly. So, how does it work?

WhozCraig
  • 65,258
  • 11
  • 75
  • 141
  • 5
    Fyi, [`std::pair`](http://en.cppreference.com/w/cpp/utility/pair) has a standard-defined [`operator <`](http://en.cppreference.com/w/cpp/utility/pair/operator_cmp), which is utilized by [`std::less`](http://en.cppreference.com/w/cpp/utility/functional/less), the default comparator for the [`std::priority_queue`](http://en.cppreference.com/w/cpp/container/priority_queue) adapter. – WhozCraig Aug 31 '17 at 21:55
  • @WhozCraig, got you. Thank you so much. :) –  Aug 31 '17 at 22:01
  • 1
    No problem. Fyi, the standard library extends this behavior to the generic [`std::tuple`](http://en.cppreference.com/w/cpp/utility/tuple/operator_cmp) variadic template, which can have an arbitrary number of elements. In case you were curious. – WhozCraig Aug 31 '17 at 22:03
  • Thank you again. If you convert that into an answer, I would be glad to accept it. –  Aug 31 '17 at 22:06

1 Answers1

2

Frankly, it works because it is designed to do so.

A few things:

  • a std::priority_queue employs std::less<T>, where T is the underlying sequence value type, as the default comparator when no override is specified.
  • std::less<T> invokes operator < against two T arguments, resolving to whatever best-fits and/or is available.

Therefore, if this works as you desired with no special override of the sequence type comparator, it must mean that there exists an operator < for std::pair<int,int> that wire this whole thing together.

And indeed there is. Checking the documentation for std::pair<T1,T2>, you'll find there is an operator < overload that effectively does this:

if (lhs.first < rhs.first)
    return true;
else if (!(rhs.first < lhs.first))
    return lhs.second < rhs.second
else
    return false;

Mind-play examples of how this works are left to the reader to think about.

WhozCraig
  • 65,258
  • 11
  • 75
  • 141