跳至主要內容

数据流的中位数：双堆维护动态中位数的完整设计

老张2026/4/30大约 8 分钟

数据流的中位数：双堆维护动态中位数的完整设计

适读人群：Java 后端工程师、算法高阶学习者 | 阅读时长：约 22 分钟 | 难度：⭐⭐⭐⭐

开篇故事

这道题是系列的收官之作。从二分查找到双指针再到滑动窗口，今天用一道综合性很强的设计题来做一个总结性的压轴。

LeetCode 295 是典型的"数据结构设计"题，考察的不是某个单一算法，而是对多个数据结构的综合运用和系统性设计能力。

我在面试 BAT 的时候被问过这道题，当时我给出了暴力解：每次加入新数后重排序，O(n log n) 的复杂度。面试官问我能不能做到 O(log n) 的 addNum 和 O(1) 的 findMedian。我愣了一会儿，然后想到了双堆。

双堆的思路非常优雅：用一个大根堆存较小的一半数据，用一个小根堆存较大的一半数据。保持两堆大小相差不超过 1，中位数就在堆顶。

一、题目解析

题目（LeetCode 295）： 中位数是有序整数列表中的中间值。如果列表大小是偶数，则中位数是中间两个数的平均值。设计一个数据结构 MedianFinder，支持：

  • addNum(int num)：将来自数据流的整数 num 添加到数据结构中。
  • findMedian()：返回目前所有元素的中位数。

示例：

MedianFinder mf = new MedianFinder();
mf.addNum(1); mf.findMedian(); // 1.0
mf.addNum(2); mf.findMedian(); // 1.5
mf.addNum(3); mf.findMedian(); // 2.0

二、解法一：维护有序列表（O(n) addNum，O(1) findMedian）

public class MedianFinder1 {
    private List<Integer> list = new ArrayList<>();

    public void addNum(int num) {
        int pos = Collections.binarySearch(list, num);
        if (pos < 0) pos = -(pos + 1);
        list.add(pos, num);  // 插入到有序位置，O(n) 移动
    }

    public double findMedian() {
        int n = list.size();
        if (n % 2 == 1) return list.get(n / 2);
        return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
    }
}

复杂度分析

  • addNum：O(n)。二分找位置 O(log n)，但 ArrayList 插入中间需要移动元素 O(n)。
  • findMedian：O(1)。
  • 空间复杂度：O(n)。

三、解法二：排序后取中值（O(n log n) addNum）

每次 addNum 后重新排序，findMedian 直接取中间。这是最简单但效率最低的方法，适合数据量小的场景。不展开代码，因为解法三更优。

四、解法三最优：双堆（O(log n) addNum，O(1) findMedian）

设计思路

维护两个堆：

  • maxHeap（大根堆）：存所有数据中较小的一半，堆顶是较小一半中最大的元素。
  • minHeap（小根堆）：存所有数据中较大的一半，堆顶是较大一半中最小的元素。

不变量：

  1. maxHeap 的所有元素 <= minHeap 的所有元素（较小半 <= 较大半）。
  2. maxHeap.size() 比 minHeap.size() 多 0 或 1（即两堆大小平衡）。

满足不变量后：

  • 总数为奇数：maxHeap.peek() 是中位数。
  • 总数为偶数：(maxHeap.peek() + minHeap.peek()) / 2.0 是中位数。

addNum 的步骤

每次插入新元素 num，需要维护不变量：

步骤：

  1. 先将 num 加入 maxHeap（确保路过 maxHeap 的过滤，让较大的元素自然流入 minHeap）。
  2. 将 maxHeap 的最大值（堆顶）弹出，加入 minHeap（保证不变量 1：maxHeap 所有元素 <= minHeap 所有元素）。
  3. 若 minHeap.size() > maxHeap.size()（违反不变量 2），将 minHeap 堆顶移回 maxHeap。

为什么步骤 1 不直接判断而是先加入 maxHeap？

如果 num 比较大，应该加入 minHeap。但我们不直接判断，而是统一"先加 maxHeap，再将 maxHeap 堆顶移给 minHeap"。这样能保证：即使 num 很大，经过 maxHeap -> minHeap 的转移，最终仍能进入正确的堆。

一个更简洁的思考方式：

  • 步骤 2 确保"maxHeap 里没有不该在里面的大元素"（大元素被推进了 minHeap）。
  • 步骤 3 确保两堆大小平衡（maxHeap 比 minHeap 多0或1个）。

Mermaid 图：addNum 流程

Mermaid 图：findMedian 流程

完整代码

public class MedianFinder {
    // 大根堆：存较小一半（Java PriorityQueue 默认小根堆，用 Collections.reverseOrder() 变大根堆）
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    // 小根堆：存较大一半
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    /**
     * 添加新数
     * 不变量维护：
     * 1. maxHeap 所有元素 <= minHeap 所有元素
     * 2. maxHeap.size() == minHeap.size() 或 maxHeap.size() == minHeap.size() + 1
     */
    public void addNum(int num) {
        // 步骤1：先加入 maxHeap
        maxHeap.offer(num);
        // 步骤2：把 maxHeap 堆顶（当前最大值）移到 minHeap（维护不变量1）
        minHeap.offer(maxHeap.poll());
        // 步骤3：若 minHeap 比 maxHeap 多，将 minHeap 堆顶移回 maxHeap（维护不变量2）
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    /**
     * 取中位数
     */
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            // 总数为奇数，中位数是 maxHeap 堆顶
            return maxHeap.peek();
        } else {
            // 总数为偶数，中位数是两堆堆顶的平均值
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }

    public static void main(String[] args) {
        MedianFinder mf = new MedianFinder();

        mf.addNum(1);
        System.out.println(mf.findMedian()); // 1.0

        mf.addNum(2);
        System.out.println(mf.findMedian()); // 1.5

        mf.addNum(3);
        System.out.println(mf.findMedian()); // 2.0

        mf.addNum(4);
        System.out.println(mf.findMedian()); // 2.5

        mf.addNum(-100);
        System.out.println(mf.findMedian()); // 2.0

        // 验证不变量
        mf.addNum(0);
        mf.addNum(100);
        System.out.println(mf.findMedian()); // 2.0 (数组排序后 [-100,0,1,2,3,4,100])
    }
}

复杂度分析

  • addNum：O(log n)。堆的插入和删除操作。
  • findMedian：O(1)。直接取堆顶。
  • 空间复杂度：O(n)。两堆共存所有元素。

五、深入分析：为什么这三步能维护不变量？

不变量 1 的维护（maxHeap 所有元素 <= minHeap 所有元素）：

步骤 2 执行后：maxHeap 的堆顶（即 maxHeap 中最大的元素）被移入 minHeap。

  • 若新加的 num <= minHeap 原堆顶：num 是 maxHeap 中最大的，把它移进 minHeap，保证 minHeap 中每个元素 >= maxHeap 中每个元素。
  • 若新加的 num > minHeap 原堆顶：num 加入 maxHeap 后成为堆顶，移入 minHeap，minHeap 收到了 num（大于原 minHeap 堆顶），不变量依然成立。

不变量 2 的维护（大小平衡）：

步骤 3 检查 minHeap 是否比 maxHeap 多，是则转移一个，恢复平衡。

六、举一反三

题号题目相关点
480滑动窗口中位数动态中位数 + 滑动窗口，需要支持删除
703数据流中的第 K 大元素单堆维护第 k 大
1670设计前中后队列数据结构设计题

滑动窗口中位数（480）的关键补丁：

480 在 295 的基础上需要支持删除旧元素，Java 的 PriorityQueue 不支持 O(log n) 删除任意元素（需要 O(n) 查找）。解决方案是使用 TreeMap<Integer, Integer> 替代堆（支持 O(log n) 删除），或者使用"懒删除"（标记删除，延迟到堆顶时才真正删除）。

七、踩坑实录

坑一：Java 中大根堆的创建方式

Java 的 PriorityQueue 默认是小根堆。要创建大根堆，需要传入 Collections.reverseOrder() 或 (a, b) -> b - a。很多初学者忘记这一步，导致两个堆的逻辑方向都是错的。

坑二：步骤 1 和 2 的顺序

必须先加入 maxHeap，再把 maxHeap 堆顶移给 minHeap，不能反过来。如果先判断 num 与 minHeap 堆顶的大小关系，代码会多出一个条件分支，而且容易在 minHeap 为空时 NPE。统一先加 maxHeap 的写法更简洁，也不需要处理空堆的特殊情况。

坑三：整数相加溢出

(maxHeap.peek() + minHeap.peek()) / 2.0 中，如果两个堆顶都接近 Integer.MAX_VALUE，相加会溢出。安全写法：maxHeap.peek() / 2.0 + minHeap.peek() / 2.0，或者先转成 long：((long)maxHeap.peek() + minHeap.peek()) / 2.0。

坑四：不变量 2 的方向搞反

不变量是 maxHeap.size() >= minHeap.size()（maxHeap 比 minHeap 多 0 或 1 个），不是 minHeap >= maxHeap。因为奇数总量时，多的那个在 maxHeap，中位数是 maxHeap 堆顶。如果把方向搞反，中位数的逻辑也要跟着反，容易出错。

坑五：只调用了 addNum 但没检查 findMedian 的奇偶性

findMedian 中，通过 maxHeap.size() > minHeap.size() 判断奇偶（maxHeap 多一个说明总数为奇数）。如果用 (maxHeap.size() + minHeap.size()) % 2 == 1 来判断也是等价的，但写法更长。两种都正确，选一种写清楚即可。

八、总结与系列收官

双堆方案是维护动态中位数的最优解，能在 O(log n) 时间内插入新数，O(1) 时间内查询中位数。

两个核心不变量：

  1. 大根堆（较小半）的所有元素 <= 小根堆（较大半）的所有元素
  2. 大根堆比小根堆多 0 或 1 个元素

每次 addNum 用三步维护不变量，findMedian 根据奇偶性取堆顶。

至此，LeetCode 二分查找、双指针与滑动窗口精讲系列（第 561-580 期）全部完成。

这 20 篇文章覆盖的核心能力：

二分查找（561-569）：

  • 左闭右闭 vs 左闭右开两种模板
  • lower_bound / upper_bound 统一框架
  • 旋转数组、峰值等非有序场景
  • 两个正序数组中位数（划分思路）
  • 二分答案（珂珂吃香蕉、D天送达、分割数组）

双指针（570-574）：

  • 有序数组两数之和的合法性证明
  • 盛水容器的贪心数学证明
  • 荷兰国旗三路划分
  • 有序数组平方（从两端向中间归并）
  • 区间列表交集（双指针处理区间）

滑动窗口（575-580）：

  • 最小长度模板（先扩张后收缩）
  • 最大长度模板（违反条件时收缩）
  • 固定窗口大小的字符频次比较
  • diff 计数器优化
  • 单调队列维护窗口最大值
  • 双堆维护动态中位数

这些是算法面试中频率最高的一组题型，掌握了这些模板，覆盖了大多数中高难度的面试题。

编辑此页
最近更新:
贡献者: xiaozhangge