时间戳

首页 > 解决方案 > 优先队列函数比较

c++ - 优先队列函数比较

问题描述

在下面的代码中，当在优先级队列中使用时，比较项是被推送的项吗？因此，在Mycomp函数中，pair &a对象是否被添加，并且pair &b，是否已经在队列中并被比较？

class Solution {
public:
    
    struct Mycomp {
        bool operator()(const pair<int, string> &a, const pair<int, string> &b){
            
            if(a.first != b.first) { // comparing the frequency if it is not same then return the one with smallest frequency
                return a.first > b.first;
            }else{
                // if frequency are same then compare the alphabetical order - should return the largest one as the idead is to pop smallest frequency with 
                // largest alphabetical order
                return a.second < b. second;
            }
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        
        //defining a map to keep track of the frequency of the words
        std::unordered_map<string, int> hashMap;

        for( auto word : words) {
            hashMap[word]++;
        }
        
        // Now we use the concept of priority queue 
        std::priority_queue<pair<int, string>,std::vector<pair<int,string>>, Mycomp> pq ;
        
        for(auto ele : hashMap) {
            pq.push({ele.second, ele.first});
            
            if(pq.size() > k) {
                pq.pop(); // pop the elements with least frequency
            }
        }
        
        vector<string> result;
        while(k--){
            result.insert(result.begin(),pq.top().second); // if you use push back, then you need to reverse the vector as pq returns the highest alpabetical order when popping.
            pq.pop();
        }
        
        return result;
    }
};

标签： c++booleancomparepriority-queue

解决方案

不，第一个参数不是要添加的对象。

你的第二个参数operator()，通常是刚刚添加的对象。

通常第一个参数是队列的中间元素。

但同样，在某些情况下，这些行为可能会出乎意料，并且取决于所使用的编译器或算法。

推荐阅读