堆 & 优先队列

堆基础

堆（二叉堆）是满足堆序性质的完全二叉树：最小堆的每个父节点 ≤ 两个子节点。C++ STL 的 priority_queue 默认是最大堆；最小堆需传 greater'<'int'>'。

操作复杂度

⚠️ pop() 无返回值：STL 的 pop() 不返回被删除元素。正确用法：先 top() 读值，再 pop() 弹出。

最大堆 vs 最小堆

Top-K 问题

维护一个大小为 K 的最小堆：扫描所有元素，若当前元素 > 堆顶则替换。扫描结束后堆中恰好是最大的 K 个元素，堆顶是第 K 大。时间 O(n log k)，空间 O(k)。

典型题目

• 215. 数组中的第 K 个最大元素
• 347. 前 K 个高频元素（先统计频次，再对频次做 Top-K）
• 373. 查找和最小的 K 对数字

// Kth largest element using min-heap of size K
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap; // min-heap
    for (int x : nums) {
        minHeap.push(x);
        if ((int)minHeap.size() > k) minHeap.pop(); // keep only k largest
    }
    return minHeap.top(); // kth largest
}

Quick Select vs 堆：Quick Select 期望 O(n) 但最坏 O(n²)；大小为 K 的堆保证 O(n log k)。若 K 远小于 n，堆更稳定；若只需第 K 大单一值，Quick Select 平均更快。

K 路合并

将 K 个已排序序列合并为一个有序序列。用最小堆：初始把每路第一个元素入堆，每次弹出最小值并将同路下一个元素入堆。总时间 O(N log K)，N 为元素总数。

典型题目

• 23. 合并 K 个升序链表
• 378. 有序矩阵中第 K 小的元素（每行视为一路）
• 786. 第 K 个最小的质数分数

// Merge K sorted arrays using min-heap
// Entry: (value, array_index, element_index)
vector<int> mergeKSorted(vector<vector<int>>& arrays) {
    using T = tuple<int,int,int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    for (int i = 0; i < (int)arrays.size(); i++)
        if (!arrays[i].empty()) pq.push({arrays[i][0], i, 0});
    vector<int> res;
    while (!pq.empty()) {
        auto [val, ai, ei] = pq.top(); pq.pop();
        res.push_back(val);
        if (ei + 1 < (int)arrays[ai].size())
            pq.push({arrays[ai][ei + 1], ai, ei + 1});
    }
    return res;
}

堆元素：堆里存 (值, 来源下标) 而不是单纯存值，这样弹出后才能找到同路的下一个元素。

滑动窗口中位数（双堆）

维护两个堆：最大堆 lo 存较小一半，最小堆 hi 存较大一半。保持 |lo| - |hi| ≤ 1 的平衡。中位数由堆顶直接读出，插入 O(log n)，删除（懒惰删除）O(log n)。

典型题目

• 295. 数据流的中位数（动态插入）
• 480. 滑动窗口中位数（插入 + 懒惰删除）

// MedianFinder — two heaps (max-heap lo, min-heap hi)
class MedianFinder {
    priority_queue<int> lo;                            // max-heap: smaller half
    priority_queue<int, vector<int>, greater<int>> hi; // min-heap: larger half
public:
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top()); lo.pop();        // balance: lo -> hi
        if (lo.size() < hi.size()) {
            lo.push(hi.top()); hi.pop();    // rebalance: hi -> lo
        }
    }
    double findMedian() {
        if (lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};

懒惰删除：C++ priority_queue 不支持随机删除。用一个 unordered_map 标记「待删」元素，在 pop 时若堆顶是待删元素则跳过，无需立刻删除——这就是懒惰删除。

任务调度

调度类问题常用最小堆追踪「最早空闲时间」：会议室问题把结束时间入最小堆，新会议到来时若堆顶 ≤ 新开始时间则弹出并复用该房间，否则新增房间。

典型题目

• 253. 会议室 II（最少会议室数）
• 621. 任务调度器（贪心 + 频次堆）
• 1834. 单线程 CPU（最短工作时间优先）

// Meeting Rooms II — minimum rooms needed
int minMeetingRooms(vector<pair<int,int>>& intervals) {
    sort(intervals.begin(), intervals.end()); // sort by start time
    priority_queue<int, vector<int>, greater<int>> endTimes; // min-heap
    for (auto& [s, e] : intervals) {
        if (!endTimes.empty() && endTimes.top() <= s)
            endTimes.pop(); // reuse room whose meeting ended
        endTimes.push(e);
    }
    return (int)endTimes.size();
}

贪心选择：调度问题的贪心性质：每次从堆中取出最小结束时间的资源，判断是否可以复用，保证整体房间数/等待时间最小。