Priority queue custom comparator

user_13587856 0
Viewed 333

below is a code for getting top K frequent elements from an array.the code is correct,but im confused about what the comparator is doing here.why is it "p1.second > p2.second " and not "p1.second < p2.second" ,shouldn't the pair with less count be the one at the top of the heap?Please help!

class Solution {
struct compare {
    bool operator() (pair<int, int>p1, pair<int, int>p2) {
        return p1.second > p2.second;
    }
};

public: vector topKFrequent(vector& nums, int k) {

    int n = nums.size();
    
    unordered_map<int, int>m;
    for (int i = 0; i < n; i++) {
        m[nums[i]]++;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare>pq;
    for (auto it = m.begin(); it != m.end(); it++) {
        pq.push(make_pair(it->first, it->second));
        if (pq.size() > k)
            pq.pop();
    }
    
    vector<int>v;
    while (!pq.empty()) {
        pair<int, int>p = pq.top();
        v.push_back(p.first);
        pq.pop();
    }
    
    return v;
**}

};**

priority-queue data-structures algorithm c++
3 Answers

By default, std::priority_queue uses the std::less comparator. In that case, pop() removes the largest element.

However, in your case you want to keep the k largest elements in the queue, and pop() the smallest one (to discard it). To do that, you need reverse the sense of the comparison.

comingstorm_2102110

What the priority queue does is constructing a heap over the container and the tail of container is the top of the heap, > means descending order so that the element with least frequency will be the top and pop first.

user_96281000

The comparator function is passed as an argument when we want to build the heap in a customized way. One node of your heap is storing two values, the element, and its frequency. Since you are using pair<int, int>, it means the first value of the pair is the element itself and the second value is its frequency. Now, inside the comparator function, you just compare two pair<int, int> according to their second value, i.e the one whose second value is larger should come first. Hence it stores the heap elements according to their frequencies.

user_120405250
Related