面试数据结构：堆与优先队列

堆是一种支持快速取最值的数据结构。

priority_queue

std::priority_queue<int> pq;

默认是大根堆。

小根堆可以这样写：

std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

常见题型

• top K 高频元素。
• 数据流中位数。
• 合并 K 个有序链表。
• 任务调度。

堆操作复杂度通常是 O(log n)。

top K 的两种做法

如果要找最大的 K 个数，可以用小根堆维护当前前 K 大：

std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
for (int x : nums) {
    heap.push(x);
    if (heap.size() > k) heap.pop();
}

堆顶是当前 K 个数里最小的那个。遍历结束后，堆里就是答案集合。

堆不是排序的替代品

如果你需要完整有序结果，排序通常更简单。如果你只需要动态维护最值或前 K 个元素，堆更合适。

面试判断

看到“第 K 大”“数据流”“实时最值”“合并多个有序序列”，应该立刻想到堆。但也要估算复杂度：堆适合 K 远小于 N 的场景。