/**
 * 1. build frequency map
 * 2. insert map entries into heap of size k
 */
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freqMap;
        for (int num : nums) {
            if (freqMap.find(num) == freqMap.end()) {
                freqMap[num] = 0;
            } else {
                freqMap[num]++;
            }
        }      

        auto comp = [&freqMap](int a, int b) {
            return freqMap[a] > freqMap[b]; 
        };

        priority_queue<int, vector<int>, decltype(comp)> pq(comp);

        for (auto& entry : freqMap) {
            pq.push(entry.first);
            if (pq.size() > k) {
                pq.pop();
            }
        }

        vector<int> output;

        while (!pq.empty()) {
            output.push_back(pq.top());
            pq.pop();
        }

        return output;
    }
};