C++ priority queue

For 2D vector, priority queue default will be sorted by the first element.

// C++ code to demonstrate sorting of a 
// 2D vector on basis of a column 
#include<iostream> 
#include<vector> // for 2D vector 
#include<algorithm> // for sort() 
#include<queue>
using namespace std;
// Driver function to sort the 2D vector 
// on basis of a particular column 
bool sortcol( const vector<int>& v1, 
   const vector<int>& v2 ) { 
return v1[1] < v2[1]; 
}
int main() 
{ 
 // Initializing 2D vector "vect" with 
 // values 
 vector< vector<int> > vect{{8, 5, 1}, 
        {9, 8, 6}, 
        {7, 2, 9}};
// Number of rows; 
 
 
 int m = vect.size();
// Number of columns (Assuming all rows 
 // are of same size). We can have different 
 // sizes though (like Java). 
 int n = vect[0].size(); 
 priority_queue<vector<int>,vector<vector<int>>> pq(vect.begin(),vect.end());
 
 cout << "The top element of this priority queue is:\n"; 
 vector<int> top_item = pq.top();
 for (auto&c:top_item)cout<<c<<" ";
 cout<<endl;
 return 0; 
}

692. Top K Frequent Words

Top K Frequent Words - LeetCode

Naively NlogN complexity algorithm without using the priority queue

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        map<string, int> m;
        for (auto word : words)
        {
            m[word]++;
        }
        vector<pair<string, int>> word_cnt;
        for (auto x : m)
        {
            word_cnt.emplace_back(x.first, x.second);
        }
        sort(word_cnt.begin(), word_cnt.end(), 
             [](pair<string, int>& a, pair<string, int>& b)
             {
                 if (a.second > b.second)  return true;
                 else if (a.second == b.second && a.first < b.first) return true;
                 else return false;
             });
        vector<string> ret(k);
        for (int i = 0; i < k; ++i)
        {
            ret[i] = word_cnt[i].first;
        }
        return ret;
    }
};

Using the priority queue to have a complexity of O(n log k)

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> freq;
        for(auto &w : words)freq[w]++;
        
        auto comp = [](const pair<string,int>& a, const pair<string,int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };
        typedef priority_queue< pair<string,int>, vector<pair<string,int>>, decltype(comp) > my_priority_queue;
        my_priority_queue  pq(comp);
        
        for(auto &w : freq ){
            pq.emplace(w.first, w.second);
            if(pq.size()>k) pq.pop();
        }
        
        vector<string> output;
        while(!pq.empty())output.push_back(pq.top().first),pq.pop();
        //while(!output.empty()){res.push_back(output.back()); output.pop_back();}
        reverse(output.begin(), output.end());
        return output;
    }
};

For this specified question, we can also use set.

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> freq;
        for(auto& w:words)freq[w]++;
        auto comp= [&](const pair<string, int> & v1,const pair<string,int> &v2) {
            return v1.second>v2.second || (v1.first<v2.first && v1.second==v2.second);
            };
        set<pair<string,int>, decltype(comp)> s(comp);
        for(auto &p:freq){
            s.emplace(p.first, p.second);
            if(s.size()>k)s.erase(--s.end());
        }
        vector<string>res;
        for(auto&e:s)res.push_back(e.first);
        return res; 
    }
};

The benefit of using set is we can update the top k on the fly. It can be used in this case: you are asked to return top k at time t1, t2, t3,…tk. Reference code is here.

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> freq, topk;
        auto comp= [&](const pair<string, int> & v1,const pair<string,int> &v2) {
            return v1.second>v2.second || (v1.first<v2.first && v1.second==v2.second);
            };
        set<pair<string,int>, decltype(comp)> s(comp);
        for(auto &w:words){
            freq[w]++;
            auto it = s.find({w,freq[w]-1});
            if(it!=s.end())s.erase(it);
            s.emplace(w,freq[w]);
            if(s.size()>k)s.erase(--s.end());
        }
        vector<string>res;
        for(auto&e:s)res.push_back(e.first);
        return res; 
    }
};

About the decltype in priority queue if lambdas is used

See [1] and [2]

Reference

[1]https://stackoverflow.com/questions/5807735/c-priority-queue-with-lambda-comparator-error

[2]https://en.cppreference.com/w/cpp/container/priority_queue