Priority queue custom comparator

Question

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;
**}

};**

shouldn't the pair with less count be the one at the top of the heap Why would the lowest be at the top? The top of a queue is the next to go, and that should be the element with the highest priority — NathanOliver
– NathanOliver, Commented Jul 2, 2020 at 15:12

comingstorm · Accepted Answer · 2020-07-15 01:36:32Z

1

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.

edited Jul 15, 2020 at 1:36

answered Jul 3, 2020 at 2:26

comingstorm

26.2k3 gold badges47 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

HypoGump · Accepted Answer · 2020-07-02 15:19:53Z

0

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.

answered Jul 2, 2020 at 15:19

HypoGump

711 silver badge11 bronze badges

Comments

Madhur Vashistha · Accepted Answer · 2020-07-02 15:43:29Z

0

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.

answered Jul 2, 2020 at 15:43

Madhur Vashistha

3291 gold badge2 silver badges7 bronze badges

Collectives™ on Stack Overflow

Priority queue custom comparator

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related