# O(nlog(k)) Priority Queue C++ code

• ``````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_t;
my_priority_queue_t  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.insert(output.begin(), pq.top().first);
pq.pop();
}
return output;
}
};
``````

• ``````        while(!pq.empty()){
output.insert(output.begin(), pq.top().first);
pq.pop();
}
``````

Inserting at the beginning of a vector with n elements takes O(n) time.

So technically this takes O(nlog(k) + k^2) time.

A better way might be to insert at the end (O(1) amortized time for each insert at the end), then reverse the output vector after the while loop.

• Same idea but using a struct as the comparator

``````class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string,int> dict;
for(const string& s:words) dict[s]++;

priority_queue<pair<string,int>, vector<pair<string,int>>, Comp> pq;
for(const auto& pa:dict) {
pq.push(pa);
if(pq.size()>k) pq.pop();
}

vector<string> result;
while(!pq.empty()) {
result.push_back(pq.top().first);
pq.pop();
}
reverse(result.begin(),result.end());
return result;
}
private:
struct Comp {
Comp() {}
~Comp() {}
bool operator()(const pair<string,int>& a, const pair<string,int>& b) {
return a.second>b.second || (a.second==b.second && a.first<b.first);
}
};

};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.