【LeetCode热题100】【堆】前 K 个高频元素

class Solution {
public:
    vector<int> ans;
    int heapSize;
    unordered_map<int, int> hash;

    void adjustHeap(int root) {
        int left = 2 * root + 1;
        int right = left + 1;
        int next = root;
        if (left < heapSize && hash[ans[left]] < hash[ans[next]])
            next = left;
        if (right < heapSize && hash[ans[right]] < hash[ans[next]])
            next = right;
        if (next != root) {
            swap(ans[next], ans[root]);
            adjustHeap(next);
        }
    }

    void buildHeap() {
        for (int i = heapSize / 2 - 1; i >= 0; --i)
            adjustHeap(i);
    }

    vector<int> topKFrequent(vector<int> &nums, int k) {
        this->heapSize = k;
        for (auto &num: nums)
            hash[num]++;
        auto &&start = hash.begin();
        while (k--) {
            ans.push_back(start->first);
            ++start;
        }
        buildHeap();
        while (start != hash.end()) {
            if (start->second > hash[ans[0]]) {
                ans[0] = start->first;
                adjustHeap(0);
            }
            ++start;
        }
        return ans;
    }
};