数据流的中位数
Find Median from Data Stream
实现 MedianFinder：不断往数据流里加数，随时返回当前所有数的中位数。
在力扣中练习题目描述
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
-
MedianFinder()初始化MedianFinder对象。 -
void addNum(int num)将数据流中的整数num添加到数据结构中。 -
double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 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(); // return 2.0
提示:
-105 <= num <= 105- 在调用
findMedian之前，数据结构中至少有一个元素 - 最多
5 * 104次调用addNum和findMedian
解题思路
对顶堆 · 双堆
左半用大顶堆，右半用小顶堆，中位数就在两个堆顶
每来一个数都重新排序太慢，中位数又只依赖有序序列的中间位置。把较小一半放在大顶堆，把较大一半放在小顶堆，两个堆顶就能守住分界。
自拟数据流依次加入 [6,-2,8,4,4,10]，每次加入后查询，结果是 [6,2,6,5,4,5]。负数、重复值和无序到达都不会改变两个不变量。
addNum(-2)：插入、搬移并恢复数量平衡，图中是真实堆结构。
左侧所有值 ≤ 右侧所有值；左堆与右堆等长，或只多一个。
首先左侧所有值不大于右侧所有值；其次左堆与右堆等长，或只比右堆多一个。代码先插入左堆，再把左堆最大值交给右堆，必要时搬回一个恢复数量平衡。
奇数个元素取左堆顶，偶数个取两个堆顶平均，除以 2.0 保留小数。图中按真实父子堆序排列，不把堆冒充完全排好序的数组；除堆顶外，兄弟节点之间不要求有序。
易错点
- 直接把 num 塞进较短的那个堆，会破坏「左堆所有数 ≤ 右堆所有数」，中位数就错了。
- findMedian 里写 (left.top() + right.top()) / 2，整数除法会把 1.5 变成 1。
- 只在 findMedian 里检查平衡是不够的：连续 add 几次后 right 会比 left 多出很多，堆顶早就偏离中间了。
有序数组 · 插入
对照版：插入 O(n)，取中位数 O(1)
结果正确，但数组插入需要 O(n)；用于对照双堆如何将插入降为 O(log n)。
把数据全部存进一个升序数组，思路最直白：
addNum：lower_bound找到第一个大于等于num的位置，insert进去；findMedian：下标直接取中间。
这个写法的查询很快，O(1)，但每次插入都要把后面一半元素整体后移，最坏 O(n)。数据流长度到 5×10⁴ 时，总代价是 O(n²)。
它适合两种场合：数据规模很小，或者插入远少于查询。放到这道题里，它正好反衬出双堆的价值 —— 双堆牺牲了一点常数，把插入压到 O(log n)。
顺带一提，lower_bound 要求区间有序，所以数组必须时刻保持升序 —— insert 插在第一个不小于 num 的位置，插完依然有序。
- 1维护一个升序 vector。
- 2addNum：lower_bound 找到插入点，insert 进去。
- 3findMedian：n 为奇数取 sorted[n/2]。
- 4n 为偶数取中间两个的平均。
易错点
- 用 push_back 后忘记排序，lower_bound 的前提就不成立了。
- 偶数长度时下标写成 n/2 和 n/2+1，会越界且取错数。
- 数据量大时 insert 的搬移会让总耗时退化成 O(n²)。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
依次加入 [6,-2,8,4,4,10]，每次加入后查询中位数左侧维护较小一半的大顶堆，右侧维护较大一半的小顶堆。
空树 · null
空树 · null
左侧所有值 ≤ 右侧所有值；左堆与右堆等长，或只多一个。
查看 C++ 代码
延伸阅读
- 双堆是「动态求第 k 大 / 中位数」的标准结构：把「有序」这个强条件换成「左右两半各自只维护一个端点」。
- 滑动窗口中位数（480）同样是双堆，只是元素会过期，需要配合哈希表做惰性删除。
- priority_queue 默认是大顶堆；小顶堆要写 priority_queue<int, vector<int>, greater<int>>，greater 来自 functional 头文件。