算法

数据流中的中位数

loser

27 Aug 2026 • 7 min read

中位数是有序整数列表中的中间值。

如果列表大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如：

arr = [2,3,4] 的中位数是 3
arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5

实现 MedianFinder 类：

MedianFinder() 初始化对象
void addNum(int num) 将数据流中的整数 num 添加到数据结构中
double findMedian() 返回到目前为止所有元素的中位数

示例 1：

输入：
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]

输出：
[null, null, null, 1.5, null, 2.0]

解释：
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr = [1, 2, 3]
medianFinder.findMedian(); // 返回 2.0

提示：

-10^5 <= num <= 10^5
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 10^4 次调用 addNum 和 findMedian

双堆：

class MedianFinder {
private:
    priority_queue<int> small;
    priority_queue<int, vector<int>, greater<int>> large;

public:
    MedianFinder() {
    }

    void addNum(int num) {
        if (small.empty() || num <= small.top())
        {
            small.push(num);
        }
        else
        {
            large.push(num);
        }

        if (small.size() > large.size() + 1)
        {
            large.push(small.top());
            small.pop();
        }
        else if (large.size() > small.size())
        {
            small.push(large.top());
            large.pop();
        }
    }

    double findMedian() {
        if (small.size() > large.size())
        {
            return small.top();
        }

        return (small.top() + large.top()) / 2.0;
    }
};

核心思想

数据流题的特点是：

元素不断加入，但不能每次都重新排序整个数组

如果每次 addNum 后都完整排序，再求中位数，代价太高。

这题最关键的观察是：

中位数只和“中间位置附近”的元素有关，不需要知道全部元素的完整顺序。

所以可以把所有数分成两部分：

左半部分：较小的一半
右半部分：较大的一半

并且让左半部分的最大值，始终不大于右半部分的最小值。

这样：

如果总数是奇数，中位数就是左半部分的最大值
如果总数是偶数，中位数就是左半部分最大值和右半部分最小值的平均值

为了快速维护这两部分，使用两个堆：

大根堆 small 保存较小的一半
小根堆 large 保存较大的一半

为什么需要两个堆

如果只用一个堆，很难同时满足：

快速找到中间位置左边的最大值
快速找到中间位置右边的最小值

两个堆正好分别承担这两个角色。

大根堆的堆顶是当前较小一半中的最大值。

小根堆的堆顶是当前较大一半中的最小值。

这两个值正好就是中位数所需要的候选。

结构约定

维护以下不变式：

small 中的元素个数要么和 large 相等，要么比 large 多 1
small 中的所有元素都不大于 large 中的所有元素

这样就能保证：

总数为奇数时，small.top() 就是中位数
总数为偶数时，small.top() 和 large.top() 分别是两个中间值

`addNum` 的插入逻辑

当插入新数字 num 时，先判断它应该放进哪一个堆。

如果 small 为空，或者：

num <= small.top()

说明它更适合放在左半部分：

small.push(num);

否则它应该放在右半部分：

large.push(num);

插入后，可能会破坏两个堆的大小平衡，所以还要调整。

调整大小

如果 small 比 large 多超过 1 个元素：

large.push(small.top());
small.pop();

如果 large 比 small 多了元素：

small.push(large.top());
large.pop();

这样就能重新满足大小平衡。

`findMedian` 的返回逻辑

如果 small 比 large 多一个元素，说明总个数是奇数。

此时中位数就是：

small.top()

如果两个堆大小相等，说明总个数是偶数。

此时中位数是两个中间值的平均数：

(small.top() + large.top()) / 2.0

注意要除以 2.0，这样结果才是浮点数。

为什么这样平衡后中位数一定正确

设当前已经插入了 n 个数。

我们维持：

small.size() == large.size() 或
small.size() == large.size() + 1

如果 n 是奇数，那么较小的一半会比较大的一半多一个元素。

这个多出来的元素正好是排序后最中间的元素，所以它就是中位数。

如果 n 是偶数，那么两边元素个数相等。

左边堆顶是左半部分最大值，右边堆顶是右半部分最小值。

它们正好是排序后中间两个数。

因此中位数是它们的平均值。

边界情况

如果只插入了一个元素：

[1]

中位数就是它本身。

如果插入两个元素：

[1, 2]

中位数是 1.5。

如果插入的数字有重复，也不会影响堆的维护。

如果插入负数，同样不影响比较和堆结构。

正确性证明

我们证明：双堆结构能正确返回当前所有元素的中位数。

结论 1：插入后，两个堆的大小始终满足平衡条件

每次插入一个数后，可能有一边比另一边多出超过 1 个元素。

算法会把某一边的堆顶移动到另一边，直到满足：

small.size() == large.size()
或者
small.size() == large.size() + 1

因此大小平衡始终成立。

结论 2：插入后，`small` 中的所有元素都不大于 `large` 中的所有元素

新数要么先进入 small，要么先进入 large。

如果它进入了不合适的一边，后续通过堆顶移动进行修正。

移动的元素总是当前一侧最接近中间位置的元素，因此不会破坏“左边都小于等于右边”的结构。

所以最终始终保持：

small 中的元素 <= large 中的元素

结论 3：当总元素个数为奇数时，中位数是 `small.top()`

根据结论 1，奇数个元素时，small 比 large 多一个元素。

根据结论 2，small 保存的是较小的一半。

所以 small.top() 就是排序后位于最中间的元素。

因此返回 small.top() 正确。

结论 4：当总元素个数为偶数时，中位数是 `small.top()` 和 `large.top()` 的平均值

根据结论 1，偶数个元素时，两个堆大小相等。

根据结论 2，small.top() 是左半部分的最大值，large.top() 是右半部分的最小值。

它们正好是排序后中间两个数。

因此中位数应为：

(small.top() + large.top()) / 2.0

得出结论

由结论 1 可知，两个堆的大小始终平衡。

由结论 2 可知，两边堆分别对应排序后的左右两半。

由结论 3 和结论 4 可知，中位数的返回公式正确。

因此双堆结构能正确维护并返回数据流中的中位数。

举例理解

以：

addNum(1)
addNum(2)
findMedian()
addNum(3)
findMedian()

为例。

插入 1 后：

small = [1]
large = []

插入 2 后：

2 进入 large
两边大小平衡

此时：

small = [1]
large = [2]

中位数是：

(1 + 2) / 2 = 1.5

再插入 3 后：

3 进入 large
large 比 small 多 1 个元素
把 large.top() 移到 small

此时：

small = [2, 1]，堆顶是 2
large = [3]

中位数是：

2

复杂度分析

设当前已经插入了 n 个元素。

每次插入只涉及堆的 push 和 pop 操作。

`addNum`

时间复杂度：O(log n)
空间复杂度：O(n)

`findMedian`

只需要读取堆顶元素。

时间复杂度：O(1)
空间复杂度：O(1)

双堆是这题最经典也最实用的做法。

双堆：