本文概览：本文讲解数据流的中位数的核心思路：大顶堆存小的一半 + 小顶堆存大的一半，两个堆顶就是中位数，O(log n) 动态维护

一、题目

image-20260906013000001

二、题目分析

1. 题目要求

要求实现一个类 MedianFinder：

  • MedianFinder()：初始化
  • addNum(num)：从数据流中添加一个整数到数据结构中
  • findMedian()：返回目前所有元素的中位数

例子：

1
2
addNum(1)  addNum(2)  →  findMedian() = 1.5
addNum(3)            →  findMedian() = 2

核心难点：数字是随机持续添加的，中位数要能随时快速查询。这不是一次性的计算，而是"边加边查"，所以需要一个能动态维护中位数的数据结构。

2. 暴力思路：有序数组 + 二分插入

第一时间的想法肯定是维护一个有序数组：新元素用二分查找找到应插入的位置，然后插进去。

  • 二分找位置：O(log n)
  • 插入后移：插入位置后面的所有元素都要往后挪，最坏 O(n)

所以整体是 O(n)，瓶颈不在找位置，在挪元素。

3. 关键观察：我们不需要完全有序

既然我们只是需要中位数，其实并不需要数组完全有序，只需要知道中间值是多少就好了。

换个角度想：把所有元素分成两半，其中一半完全小于另一半：

1
2
3
4
小的一半                       大的一半
[1, 3, 5, 7]                  [9, 11, 13, 15]

max = 7  ←— 分界 —→  min = 9
  • 总长度为偶数时：中位数 = (小的一半的最大值 + 大的一半的最小值) / 2，即 (7 + 9) / 2 = 8
  • 总长度为奇数时：设立一个规则——小的那一半可以多存一个元素，中位数就是小的一半的最大值

这样只要随时拿到"小的一半的最大值"和"大的一半的最小值"这两个数，中位数就出来了。

4. 用什么维护两半的最大最小值？

普通数组拿最大最小值都要 O(n) 扫一遍，不够快。

  • 小的一半要快速拿最大值 → 最大堆（堆顶就是这一半的最大值）
  • 大的一半要快速拿最小值 → 最小堆（堆顶就是这一半的最小值）

堆的插入/弹出都是 O(log n)，正好满足"比 O(n) 快的维护"。

最大堆、最小堆的详细介绍可以看我另一篇题解（物理数组 + 逻辑完全二叉树、上浮、下沉的完整推导），这里不再重复：

三、思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MedianFinder {
    private PriorityQueue<Integer> minHeap;   // 大的一半（堆顶 = 大一半的最小值）
    private PriorityQueue<Integer> maxHeap;   // 小的一半（堆顶 = 小一半的最大值）

    public MedianFinder() {
        minHeap = new PriorityQueue<>();
        maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    }

    public void addNum(int num) {
        if (minHeap.size() != maxHeap.size()) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}

思路简要说明：

  1. 两个堆分工：maxHeap（最大堆）存小的一半，minHeap（最小堆）存大的一半
  2. 数量规则：总元素为奇数时，maxHeap 比 minHeap 多存一个（中位数取 maxHeap 堆顶）
  3. 平衡插入：每来一个新元素都过一遍两个堆（先加进一个堆、弹出堆顶、给另一个堆），确保两半的大小关系和数量规则始终成立
  4. **查询 O(1)**：偶数取两堆顶平均，奇数取 maxHeap 堆顶
  5. **时间复杂度 O(log n)**：addNum 涉及 3 次堆操作，每次 O(log n)

四、思路详解

第一步：为什么"分两半"就能拿到中位数？

中位数的定义：所有元素排序后处在正中间的值。

  • 偶数个：正中间两个数的平均值
  • 奇数个：正中间那一个数

而"小的一半完全小于大的一半"这个划分，恰好把正中间的两个数暴露在分界线上：

1
2
3
4
5
6
7
8
9
排序后：[1, 3, 5, | 7, 9, 11]      ← 偶数 6 个
                 ↑     ↑
          小一半的max   大一半的min
          中位数 = (5 + 7) / 2 = 6

排序后：[1, 3, 5, 7, | 9, 11]      ← 奇数 5 个，小一半多存一个
                    ↑
             小一半的max
             中位数 = 7

所以只要"分界线两侧的最大值/最小值"随时可查，中位数就随时可查，其余元素怎么排根本不用关心。

第二步：为什么要约定"奇数时小的一半多存一个"？

奇数个元素没法平分，两半必然一边多一个，必须提前定死规则，查询时才知道取谁的堆顶。

约定"小的那一半多一个"的好处：findMedian 里奇数分支直接 return maxHeap.peek()，一个堆顶就是答案。

（反过来约定"大的一半多一个"也完全可行，查询时取 minHeap 堆顶即可，本文代码采用前者。）

第三步：addNum 的插入逻辑——最巧妙的点

先看代码：

1
2
3
4
5
6
7
8
9
10
11
public void addNum(int num) {
    if (minHeap.size() != maxHeap.size()) {
        // 不相等（maxHeap 多 1 个）→ 目标：给 minHeap 补 1 个
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
    } else {
        // 相等 → 目标：给 maxHeap 补 1 个
        minHeap.offer(num);
        maxHeap.offer(minHeap.poll());
    }
    }

为什么不能直接往对应的堆里塞？

因为有个铁律必须满足：minHeap 的所有元素 > maxHeap 的所有元素（大的一半完全大于小的一半）。直接塞新元素，可能破坏这条性质——万一新元素很小，却塞进了大的一半呢？

解决方式：让新元素"过一遍对面那个堆"再落位。

分两种情况推演（注意数量规则：maxHeap 比 minHeap 多 0 或 1 个）：

情况一：两堆相等 → 这次要让 maxHeap 多 1 个

1
2
3
4
5
6
7
8
9
直接塞 maxHeap 的风险：num 可能很大，比 minHeap 的某些元素还大 → 违反铁律

正确做法：
  1. minHeap.offer(num)      ← 先塞进对面（大的一半）
  2. maxHeap.offer(minHeap.poll())  ← 弹出大一半的最小值，给小的一半

  num 如果真的很大 → 它留在 minHeap 里（大的一半），完全合法
  num 如果其实很小 → 它就是 minHeap 弹出来的那个，去了 maxHeap（小的一半），也合法
  num 不大不小 → poll 出来的是原有的某个更小元素，同样两边都合法

关键：minHeap.poll() 弹出的元素，是"大的一半"里最小的，它必然 ≤ minHeap 里剩下的所有元素，把它给 maxHeap，铁律必然保持。新元素无论大小，都会被自动路由到正确的半区。

情况二：maxHeap 多 1 个 → 这次要让 minHeap 补 1 个（回到相等）

1
2
3
4
5
6
7
8
直接塞 minHeap 的风险：num 可能很小，比 maxHeap 的某些元素还小 → 违反铁律

正确做法：
  1. maxHeap.offer(num)      ← 先塞进对面（小的一半）
  2. minHeap.offer(maxHeap.poll())  ← 弹出小一半的最大值，给大的一半

  同理：maxHeap.poll() 弹出的是"小的一半"里最大的，必然 ≥ maxHeap 剩下的所有元素
  给 minHeap，铁律必然保持

总结这个设计的巧妙之处：

  • 新元素不直接落位，先进入对面的堆"排队"，由堆顶机制筛出该跨过分界线的那个元素
  • 3 次堆操作（offer + poll + offer），换来"数量规则 + 大小铁律"同时被维护，不需要任何 if 判断新元素的大小
  • 条件极简：只看两堆 size 是否相等，不用比较 num 和堆顶

第四步：findMedian 的取值

1
2
3
4
5
6
7
8
9
public double findMedian() {
    if (maxHeap.size() == minHeap.size()) {
        // 偶数：两堆顶平均（注意 2.0 避免整数除法）
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    } else {
        // 奇数：小的一半多一个，堆顶就是中位数
        return maxHeap.peek();
    }
}

对应第二步的规则约定：

  • 偶数：小一半的 max（maxHeap 堆顶）+ 大一半的 min（minHeap 堆顶），除以 2.0
  • 奇数：maxHeap 多一个，堆顶即中位数

第五步：能否优化到 1 次堆操作？

上面的写法每次 addNum 固定 3 次堆操作。其实有些情况下新元素可以直接落位，省到 1 次：

1
2
3
4
5
6
7
8
9
10
11
情况A: max.size()==min.size() && num < min.peek()
  → 仅 max.offer(num)                    ← 1次堆操作 ✅

情况B: max.size()==min.size() && num >= min.peek()
  → min.offer + min.poll + max.offer     ← 3次堆操作

情况C: max.size()>min.size() && num > max.peek()
  → 仅 min.offer(num)                    ← 1次堆操作 ✅

情况D: max.size()>min.size() && num <= max.peek()
  → max.offer + max.poll + min.offer     ← 3次堆操作

思路：先拿 num 和堆顶比一比，如果 num 天然属于目标半区（比大一半的最小值还小 / 比小一半的最大值还大），直接塞进去就行，不用绕对面一圈。

但是不建议这样写：

  • 四个条件分支很容易写错、写漏（比如边界用 < 还是 <=）
  • 省下的只是常数时间（O(log n) 不变），换来的是正确性风险
  • 对称的 3 次操作写法无脑且必然正确，面试和实战都更稳

大家感兴趣可以自己完成这部分代码，本文不提供。

完整执行过程

依次添加 [1, 2, 3, 4, 5]，每步列出两堆状态（括号标注堆顶）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
初始：maxHeap = []，minHeap = []

addNum(1)：两堆相等(0==0)
  minHeap.offer(1) → [1]
  maxHeap.offer(minHeap.poll()) → maxHeap=[1]，minHeap=[]
  maxHeap: (1)        minHeap: —

addNum(2)：两堆不等(1!=0)，maxHeap 多 1
  maxHeap.offer(2) → [1, 2]
  minHeap.offer(maxHeap.poll()) → minHeap=[2]，maxHeap=[1]
  maxHeap: (1)        minHeap: (2)
  铁律检查：max=1 < min=2 ✓

addNum(3)：两堆相等(1==1)
  minHeap.offer(3) → [2, 3]
  maxHeap.offer(minHeap.poll()) → maxHeap=[1,2]，minHeap=[3]
  maxHeap:   2
           /
         (1)           minHeap: (3)
  铁律检查：max堆顶2 < min堆顶3 ✓

addNum(4)：两堆不等(2!=1)，maxHeap 多 1
  maxHeap.offer(4) → [1, 2, 4]
  minHeap.offer(maxHeap.poll()) → minHeap=[3,4]，maxHeap=[1,2]
  maxHeap:   2
           /
         (1)           minHeap: (3)
                        \
                         4
  铁律检查：max堆顶2 < min堆顶3 ✓

addNum(5)：两堆相等(2==2)
  minHeap.offer(5) → [3, 4, 5]
  maxHeap.offer(minHeap.poll()) → maxHeap=[1,2,3]，minHeap=[4,5]
  maxHeap:   (3)
           /   \
          1     2         minHeap: (4)
                              \
                               5
  铁律检查：max堆顶3 < min堆顶4 ✓

验证中位数查询：
addNum(2) 后：总 2 个（偶数）→ (1 + 2) / 2.0 = 1.5 ✓
addNum(3) 后：总 3 个（奇数）→ maxHeap 堆顶 = 2 ✓
addNum(4) 后：总 4 个（偶数）→ (2 + 3) / 2.0 = 2.5 ✓
addNum(5) 后：总 5 个（奇数）→ maxHeap 堆顶 = 3 ✓

复杂度分析

时间复杂度：

  • addNum：O(log n)，固定 3 次堆操作（offer + poll + offer），每次 O(log n)
  • findMedian：O(1)，只 peek 两个堆顶

**空间复杂度 O(n)**：两个堆合计存全部元素。

对比有序数组方案：addNum O(n)（挪元素）+ findMedian O(1)。堆方案把插入的 O(n) 压到 O(log n)，这正是动态数据流场景下需要的。

五、总结

数据流的中位数的核心思路：

  1. 分两半：小的一半 + 大的一半，一半完全小于另一半，不追求完全有序
  2. 两堆分工：小的一半用最大堆（堆顶 = 小一半 max），大的一半用最小堆（堆顶 = 大一半 min）
  3. 数量规则：奇数时 maxHeap 多存一个，中位数 = maxHeap 堆顶
  4. 平衡插入：新元素先 offer 进对面堆、poll 出堆顶给目标堆，3 次堆操作同时维护数量规则和大小铁律
  5. **查询 O(1)**：偶数两堆顶平均 / 2.0，奇数取 maxHeap 堆顶

对顶堆的适用场景：

  • 动态数据流的中位数
  • 滑动窗口中位数
  • 任何"把数据分成一大一小两部分，随时要拿中间分界值"的场景

这个套路叫对顶堆：两个堆顶相对而立，中间那条缝就是分界线。