力扣hot100——347.前K个高频元素（cpp手撕堆）

题目链接：347. 前 K 个高频元素 - 力扣（LeetCode）

cpp版手撕堆

class Solution {
public:
    // 向下调整堆（最小堆）
    void shiftDown(vector<pair<int, int>>& heap, int index,int len) {
        int parent = index;
        int child = 2 * parent + 1;
        while (child < len) {
            if (child + 1 < len && heap[child + 1].second < heap[child].second) {
                child++;
            }
            if (heap[parent].second > heap[child].second) {
                swap(heap[parent], heap[child]);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 统计每个数字出现的频率
        unordered_map<int, int> freqMap;
        for (int num : nums) {
            freqMap[num]++;
        }
        // 初始化堆，放入前 k 个元素
        vector<pair<int, int>> minHeap;
        for (const auto& entry : freqMap) {
            if (minHeap.size() < k) {
                minHeap.push_back(entry);
            }
        }
        // 构造一个合法的最小堆
        for (int i = minHeap.size() / 2 - 1; i >= 0; i--) {
            shiftDown(minHeap, i,k);
        }
        // 处理剩下的元素
        int processedCount = 0;
        for (const auto& entry : freqMap) {
            if (processedCount < k || entry.second <= minHeap[0].second) {
                processedCount++;
                continue;
            }
            minHeap[0] = entry;
            shiftDown(minHeap, 0,k);
        }
        // 提取结果
        vector<int> result;
        for (const auto& p : minHeap) {
            result.push_back(p.first);
        }
        return result;
    }
};