堆与优先队列：Top K 与中位数

这一课你将能做到

1. 说清堆的两种形态（小顶堆、大顶堆）以及插入、取顶的复杂度
2. 用大小为 K 的小顶堆解决第 K 大 / 前 K 高频问题，并判断何时用桶排序
3. 用两个堆维护数据流中位数，解释为什么这样能保持平衡

为什么要学

普通队列是先进先出，优先队列（Priority Queue）则是「每次取当前最优先的元素」，底层就是堆。任务调度里高优先级任务先跑、订单超时扫描、Dijkstra 最短路每次取当前最近节点，靠的都是它。

面试中堆的考法非常集中：Top K 系列和数据流中位数。为什么不用排序一把梭？因为「第 K 大」只关心前 K 个，维护一个 K 大小的堆是 O(n log K)，比全排序 O(n log n) 更省；而且面对源源不断到来的数据流，你不可能每来一个数就整体排序，堆却可以增量地 O(log n) 维护。理解堆，就补上了「在线处理」这块思维拼图。

先建立图像

堆是一棵完全二叉树，逻辑是树、物理存储是数组：

小顶堆           数组表示（下标 0 起）：
    1              [1, 3, 2, 7, 9]
   / \            父 i，子 2i+1 / 2i+2
  3   2           子 i，父 (i-1)/2
 / \
7   9

规则：小顶堆的每个父节点 ≤ 子节点，所以堆顶永远是全局最小；大顶堆反之。插入和取顶都通过「上浮 / 下沉」恢复堆序，O(log n)；peek 为 O(1)。

Java 中：

Queue<Integer> minHeap = new PriorityQueue<>();             // 默认小顶堆
Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

跟着做

步骤 1：LeetCode 215「数组中的第 K 个最大元素」（中等）

如 [3,2,1,5,6,4]、K=2，返回 5。

思路：维护一个大小为 K 的小顶堆，遍历数组往里放；堆大小超过 K 就弹出最小的。走完后，堆里是全体最大的 K 个数，堆顶恰好是其中最小的——即第 K 大。

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> heap = new PriorityQueue<>(k);
        for (int x : nums) {
            heap.offer(x);
            if (heap.size() > k) {
                heap.poll(); // 踢掉最小的，保住最大的 k 个
            }
        }
        return heap.peek();
    }
}

逐点讲：为什么用小顶堆而不是大顶堆？因为要不断淘汰「K 个候选里最小的」，小顶堆的堆顶正好提供它。时间 O(n log K)，空间 O(K)。

补充：LeetCode 215 最优理论解法是快速选择（Quick Select），平均 O(n)，但最坏 O(n²)、实现易出边界问题。面试给堆解稳妥、够用，能口述 Quick Select 作为加分。

步骤 2：LeetCode 347「前 K 个高频元素」（中等）

返回出现频率前 K 高的元素。

两步走：先用 HashMap 统计频次，再按频次维护大小为 K 的小顶堆。

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) {
            freq.merge(x, 1, Integer::sum);
        }
        // 小顶堆按频次排序，堆顶是候选里频次最低的
        Queue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(freq::get));
        for (int key : freq.keySet()) {
            heap.offer(key);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        return heap.stream().mapToInt(Integer::intValue).toArray();
    }
}

时间 O(n log K)，空间 O(n)。

进阶：题目数据频次范围是 1～n，可以用桶排序——按频次分桶（List<Integer>[] buckets），从高频桶往低取 K 个，整体 O(n)。这是面试官追问「还能更快吗」的标准答案。

步骤 3：LeetCode 295「数据流的中位数」（困难）

设计一个数据结构，持续 addNum 添加整数，并能随时 findMedian 返回当前所有数的中位数。

思路：两个堆配合。

• low：大顶堆，存较小的一半，堆顶是这一半里最大的；
• high：小顶堆，存较大的一半，堆顶是这一半里最小的。

维护两条不变量：low 的大小等于 high，或恰好多 1；且 low 堆顶 ≤ high 堆顶。这样偶数个时中位数 = 两堆顶平均，奇数个时 = low 堆顶。

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

class MedianFinder {
    private final Queue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
    private final Queue<Integer> high = new PriorityQueue<>();

    public MedianFinder() {
    }

    public void addNum(int num) {
        low.offer(num);              // 先进 low
        high.offer(low.poll());      // low 的最大值移交 high，保证 low ≤ high
        if (low.size() < high.size()) {
            low.offer(high.poll());  // 平衡：low 必须不少得
        }
    }

    public double findMedian() {
        if (low.size() > high.size()) {
            return low.peek();      // 奇数，中位在 low 顶
        }
        return (low.peek() + high.peek()) / 2.0;
    }
}

逐点讲：插入经过「low → high → 必要时回流」，用两次堆操作自动归位，比手写一堆 if 判断大小关系更不易错。addNum O(log n)，findMedian O(1)，空间 O(n)。

讲清楚要点

1. Top K 用 K 大小的小顶堆：堆顶是候选中的最弱项，超员即淘汰，这是统一模板；求前 K 小则反过来用大顶堆。
2. 堆解的复杂度统一是 O(n log K)：K 接近 n 时退化到 O(n log n)，不如排序；K 很小时优势最大。
3. 双堆问题的核心是「不变量」：大小关系和值域关系必须时刻成立，插入逻辑只为维护它服务。
4. 堆适合在线 / 流式场景：数据分批到来时无需重算，这是排序做不到的。
5. Comparator.comparingInt(map::get) 是按 map 值排序堆元素的常用写法，347 题直接套用。

你可能会懵的地方

• 堆看起来是树，为什么存数组就行？ 完全二叉树没有空洞，父子位置可以用下标公式精确换算，不需要真存指针，数组最省空间。

• 求第 K 大为什么不用大顶堆全部装？ 大顶堆全装后要弹出 K 次才到第 K 大，等于 O(n + K log n)，且堆要 O(n) 空间；小顶堆限 K，始终 O(K) 空间，流式场景尤其关键。

• 中位数插入时为什么要先 low 再 high 绕一圈？ 直接判断该进哪边需要多处比较。先走 low 再把 low 最大交给 high，保证了「小的进 low、大的进 high」的序，再用一次回流修平大小，逻辑短且无死角。

• 两堆顶相加会溢出 int 怎么办？ 转 long 相加再 /2.0，或像本题那样除以 2.0 时先提升运算精度（极端 int 极值仍建议先转 long：((long) low.peek() + high.peek()) / 2.0）。

• PriorityQueue 可以放重复值吗？是 Set 吗？ 可以重复，它是队列不是 Set；相同频次的不同元素也都能共存。

错法对照

错法	问题	正解
Top K 先全排序再取前 K	O(n log n) + O(n) 空间	K 大小堆 O(n log K)
第 K 大用大顶堆后 peek	peek 永远是最大值不是第 K 大	小顶堆保 K 个取堆顶
中位数不维护两堆大小差	无法确定取哪个堆顶	low 大小等于或恰多 1
addNum 直接按 if 分流且不交叉校验	可能破坏 low 顶 ≤ high 顶	经 low→high 再回流
中位数奇数时取两堆平均	定义用错	奇数取 low 顶，偶数平均

卡点急救

1. 堆顶元素不是想要的答案：先确认建的是哪种堆。淘汰最小值用小顶堆，淘汰最大值用大顶堆，90% 的困惑来自建反。
2. 347 比较器不会写：PriorityQueue 构造里给 Comparator.comparingInt(freq::get)，意思是「比较这个 key 在 freq 表里的值」。
3. 中位数两堆越用越失衡：只看不变量——每次 add 结束后 low 顶 ≤ high 顶、low 大小 ∈ {high 大小, high 大小+1}，不满足就是插入顺序写错。

面试常问

• Top K 如果数据量单机放不下怎么办？ 分布式小顶堆：每台机器各自维护 K 大小堆，汇总时把各机器的 K 个候选合并（共 mK 个），再做一次总堆。这是 MapReduce 思想，日志热词统计的标准架构。

• PriorityQueue 的底层为什么 offer/poll 是 O(log n)？ 插入到数组末尾后「上浮」与父节点比较交换；取走堆顶后用末尾元素补位并「下沉」，路径长度等于树高 log n。

• 如何实时求滑动窗口内的最大值（LeetCode 239）？ 堆可以做：元素连同下标入大顶堆，弹出窗口外的过期堆顶，peek 即答案，O(n log n)。更优是单调双端队列 O(n)（窗口课已提），面试能比较两种方案更佳。

自测三问

1. 小顶堆和大顶堆分别在什么时候用？第 K 大为什么选小顶堆？
2. 347 题从 O(n log K) 优化到 O(n) 用了什么方法？
3. 中位数双堆的两条不变量是什么？插入时如何维护？

小结一句话

堆解决「反复取最」：Top K 用 K 大小堆淘汰最弱、频次题可换桶排序 O(n)，中位数用双堆分区、答案永远在两个堆顶之间。

延伸

• 巩固练习：LeetCode 703 数据流中的第 K 大元素、LeetCode 692 前 K 个高频单词、LeetCode 973 最接近原点的 K 个点
• 把代码提交到本站在线判题平台，注意中位数题两个数相差很大时的精度
• 下一课预告：回溯——系统性枚举所有可能，全排列、子集、N 皇后与剪枝