LeetCode 295困难堆 · 对顶堆
数据流的中位数 图解题解
这道题到底在问什么
设计一个数据结构，支持 addNum(x) 把数加入数据流，findMedian() 返回当前所有数的中位数（奇数个取正中间，偶数个取中间两数的平均）。
- 输入
- addNum(5) → addNum(15) → addNum(1)
- 输出
- 中位数 5
最优解：一步一步想明白
- 3核心一句话：大顶堆装小的一半、小顶堆装大的一半，两堆大小差 ≤1，中位数就在两个堆顶。
- 4开局两个堆都是空的。约定：每来一个数 x，先放进大顶堆 lo，再把 lo 的堆顶匀给小顶堆 hi，最后平衡两堆大小。
- 5现在看大顶堆。第 1 个数 5 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 5 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = —。
- 6切到看小顶堆。把 lo 的堆顶 5 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 5 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = —。
- 7切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 5 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 5，hi 顶 = —。
- 8平衡完成：共 1 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 5。此刻两堆顶：lo 顶 5、hi 顶 —，都列在右侧面板里。
- 9现在看大顶堆。第 2 个数 15 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 15 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = —。
- 10切到看小顶堆。把 lo 的堆顶 15 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 15 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
- 11平衡完成：共 2 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 5 + 🔻hi 顶 15) / 2 = 10。两个堆顶都在右侧面板里同时可见。
- 12现在看大顶堆。第 3 个数 1 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 5 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 15。
- 13切到看小顶堆。把 lo 的堆顶 5 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 5 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 1。
- 14切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 5 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 5，hi 顶 = 15。
- 15平衡完成：共 3 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 5。此刻两堆顶：lo 顶 5、hi 顶 15，都列在右侧面板里。
- 16现在看大顶堆。第 4 个数 3 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 5 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 15。
- 17切到看小顶堆。把 lo 的堆顶 5 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 5 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 3。
- 18平衡完成：共 4 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 3 + 🔻hi 顶 5) / 2 = 4。两个堆顶都在右侧面板里同时可见。
- 19现在看大顶堆。第 5 个数 8 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 8 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 5。
- 20切到看小顶堆。把 lo 的堆顶 8 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 5 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 3。
- 21切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 5 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 5，hi 顶 = 8。
- 22平衡完成：共 5 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 5。此刻两堆顶：lo 顶 5、hi 顶 8，都列在右侧面板里。
- 23现在看大顶堆。第 6 个数 7 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 7 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 8。
- 24切到看小顶堆。把 lo 的堆顶 7 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 7 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
- 25平衡完成：共 6 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 5 + 🔻hi 顶 7) / 2 = 6。两个堆顶都在右侧面板里同时可见。
- 26现在看大顶堆。第 7 个数 9 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 9 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 7。
- 27切到看小顶堆。把 lo 的堆顶 9 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 7 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
- 28切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 7 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 7，hi 顶 = 8。
- 29平衡完成：共 7 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 7。此刻两堆顶：lo 顶 7、hi 顶 8，都列在右侧面板里。
- 30现在看大顶堆。第 8 个数 2 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 7 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 8。
- 31切到看小顶堆。把 lo 的堆顶 7 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 7 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
- 32平衡完成：共 8 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 5 + 🔻hi 顶 7) / 2 = 6。两个堆顶都在右侧面板里同时可见。
- 33现在看大顶堆。第 9 个数 6 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 6 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 7。
- 34切到看小顶堆。把 lo 的堆顶 6 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 6 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
- 35切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 6 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 6，hi 顶 = 7。
- 36平衡完成：共 9 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 6。此刻两堆顶：lo 顶 6、hi 顶 7，都列在右侧面板里。
- 37现在看大顶堆。第 10 个数 10 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 10 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 7。
- 38切到看小顶堆。把 lo 的堆顶 10 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 7 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 6。
- 39平衡完成：共 10 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 6 + 🔻hi 顶 7) / 2 = 6.5。两个堆顶都在右侧面板里同时可见。
- 40全部 10 个数加完（本侧画的是🔻小顶堆）。无论流多长，中位数永远夹在「🔺大顶堆顶 6」和「🔻小顶堆顶 7」之间，findMedian 只看这两个堆顶，O(1) 就能报出。
⚠️ 容易写错的地方
✗ 错：只用一个堆 / 一个有序数组
✓ 对：对顶双堆
单堆取中间要 O(n) 找位置；双堆把中位数永远顶在堆顶
✗ 错：加完不平衡，两堆大小差 > 1
✓ 对：每次加完检查并匀一个回去
大小差 >1 时堆顶就不是中位数了
✗ 错：偶数个时只取一个堆顶
✓ 对：偶数取两个堆顶的平均
偶数个中位数是中间两数的平均，缺一不可
✗ 错：lo/hi 装反（lo 装大的）
✓ 对：lo 大顶堆装小一半、hi 小顶堆装大一半
装反会导致堆顶不再相邻于中位数
完整代码（Python / C++ / Java）
Python
import heapq
class MedianFinder:
def __init__(self):
self.lo = [] # 大顶堆(存负数模拟)，装较小一半
self.hi = [] # 小顶堆，装较大一半
def addNum(self, x):
heapq.heappush(self.lo, -x) # 先入 lo
heapq.heappush(self.hi, -heapq.heappop(self.lo)) # lo 顶匀给 hi
if len(self.hi) > len(self.lo): # 平衡大小
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def findMedian(self):
if len(self.lo) > len(self.hi):
return -self.lo[0] # 奇数：lo 顶
return (-self.lo[0] + self.hi[0]) / 2 # 偶数：两顶平均C++
class MedianFinder {
priority_queue<int> lo; // 大顶堆，较小一半
priority_queue<int,vector<int>,greater<int>> hi; // 小顶堆，较大一半
public:
void addNum(int x){
lo.push(x);
hi.push(lo.top()); lo.pop(); // lo 顶匀给 hi
if(hi.size() > lo.size()){ lo.push(hi.top()); hi.pop(); }
}
double findMedian(){
if(lo.size() > hi.size()) return lo.top();
return (lo.top() + hi.top()) / 2.0;
}
};Java
class MedianFinder {
PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // 大顶堆
PriorityQueue<Integer> hi = new PriorityQueue<>(); // 小顶堆
public void addNum(int x){
lo.offer(x);
hi.offer(lo.poll()); // lo 顶匀给 hi
if(hi.size() > lo.size()) lo.offer(hi.poll());
}
public double findMedian(){
if(lo.size() > hi.size()) return lo.peek();
return (lo.peek() + hi.peek()) / 2.0;
}
}复杂度
addNum
O(log n)
每次最多 3 次堆的 push/pop，每次 O(log n)
findMedian
O(1)
只读两个堆顶，不做任何遍历
空间
O(n)
所有数分装在两个堆里
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 数据流的中位数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果要求第 k 百分位数（不是中位数），这套双堆还能用吗？+
可以推广：把两堆大小比例从 1:1 改成对应百分位的比例（如 90 分位维持 9:1），每次加数后按目标比例平衡，分位点就落在两个堆顶之间。
数据流非常大、内存放不下怎么办？+
改用近似算法（如 t-digest、Count-Min 配合采样）或在磁盘/分布式上分桶统计，用 O(1)~O(log) 的概要结构估计分位数，牺牲少量精度换内存。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 数据流的中位数 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。