Top K elements

topKFrequent.cpp

//max heap
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> um;
    for(auto num : nums)
        um[num]++;
    vector<int> res;
    priority_queue<pair<int,int>>pq; //max heap
    for(auto it = um.begin(); it != um.end(); it++){
        pq.push(make_pair(it->second, it->first)); //(occurence, element), sort by occurence
        if(pq.size() > um.size() - k){ //um.size() is the number of unique element, 1 <= k <= um.size().
            res.push_back(pq.top().second); //element
            pq.pop();
        }
    }
    return res;
}

//min heap
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> um;
    for(auto num : nums)
        um[num]++;
    vector<int> res;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>pq; //min heap
    for(auto it = um.begin(); it != um.end(); it++){
        pq.push(make_pair(it->second, it->first)); //(occurence, element), sort by occurence
        if(pq.size() > k)
            pq.pop();
    }
    while(!pq.empty()){
        res.push_back(pq.top().second);
        pq.pop();
    }
    return res;
}