class Solution {
public:
/**
* return topK string
* @param strings string字符串vector strings
* @param k int整型 the k
* @return string字符串vector<vector<>>
*/

/*
// 小根堆，头部是小的
struct cmp{
bool operator()(const pair<string, int>& p1, const pair<string, int>& p2 ){
return(p1.second>p2.second || (p1.second==p2.second && p1.first<p2.first));
}
};

vector<vector<string> > topKstrings(vector<string>& strings, int k) {
// write code here
vector<vector<string>> res;
unordered_map<string, int> umap;
for(auto ele:strings){
umap[ele]+=1;
}

// 优先级队列表示堆
priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;
for(const auto& ele:umap){
if(pq.size()<k){
pq.emplace(pair<string, int>(ele.first, ele.second));
}
else if( ele.second>pq.top().second || (ele.second==pq.top().second && ele.first<pq.top().first) ){
pq.pop();
pq.emplace(pair<string, int>(ele.first, ele.second));
}
}
while(!pq.empty()){
res.push_back(vector<string> {pq.top().first, to_string(pq.top().second)});
pq.pop();
}

reverse(res.begin(), res.end());

return res;


}
*/


// 大根堆，头部是大的，
struct cmp{
bool operator()(const pair<string, int>& p1, const pair<string, int>& p2 ){
return(p1.second<p2.second || (p1.second==p2.second && p1.first>p2.first));
}
};

vector<vector<string> > topKstrings(vector<string>& strings, int k) {
// write code here
vector<vector<string>> res;
unordered_map<string, int> umap;
for(auto ele:strings){
umap[ele]+=1;
}

// 优先级队列表示堆，将map中的所有元素放进去
priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;
for(const auto& ele:umap){
pq.emplace(pair<string, int>(ele.first, ele.second));
}

int i = 0;
while(!pq.empty() && i<k){
res.push_back(vector<string> {pq.top().first, to_string(pq.top().second)});
pq.pop();
i++;
}

//         reverse(res.begin(), res.end());

return res;


}
};