题目描述
思路解析动画文字版
核心一句话：大顶堆装小的一半、小顶堆装大的一半，两堆大小差 ≤1，中位数就在两个堆顶。
开局两个堆都是空的。约定：每来一个数 x，先放进大顶堆 lo，再把 lo 的堆顶匀给小顶堆 hi，最后平衡两堆大小。
现在看大顶堆。第 1 个数 5 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 5 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = —。
切到看小顶堆。把 lo 的堆顶 5 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 5 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = —。
切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 5 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 5，hi 顶 = —。
平衡完成：共 1 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 5。此刻两堆顶：lo 顶 5、hi 顶 —，都列在右侧面板里。
现在看大顶堆。第 2 个数 15 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 15 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = —。
切到看小顶堆。把 lo 的堆顶 15 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 15 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
平衡完成：共 2 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 5 + 🔻hi 顶 15) / 2 = 10。两个堆顶都在右侧面板里同时可见。
现在看大顶堆。第 3 个数 1 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 5 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 15。
切到看小顶堆。把 lo 的堆顶 5 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 5 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 1。
切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 5 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 5，hi 顶 = 15。
平衡完成：共 3 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 5。此刻两堆顶：lo 顶 5、hi 顶 15，都列在右侧面板里。
现在看大顶堆。第 4 个数 3 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 5 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 15。
切到看小顶堆。把 lo 的堆顶 5 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 5 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 3。
平衡完成：共 4 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 3 + 🔻hi 顶 5) / 2 = 4。两个堆顶都在右侧面板里同时可见。
现在看大顶堆。第 5 个数 8 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 8 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 5。
切到看小顶堆。把 lo 的堆顶 8 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 5 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 3。
切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 5 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 5，hi 顶 = 8。
平衡完成：共 5 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 5。此刻两堆顶：lo 顶 5、hi 顶 8，都列在右侧面板里。
现在看大顶堆。第 6 个数 7 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 7 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 8。
切到看小顶堆。把 lo 的堆顶 7 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 7 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
平衡完成：共 6 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 5 + 🔻hi 顶 7) / 2 = 6。两个堆顶都在右侧面板里同时可见。
现在看大顶堆。第 7 个数 9 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 9 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 7。
切到看小顶堆。把 lo 的堆顶 9 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 7 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 7 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 7，hi 顶 = 8。
平衡完成：共 7 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 7。此刻两堆顶：lo 顶 7、hi 顶 8，都列在右侧面板里。
现在看大顶堆。第 8 个数 2 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 7 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 8。
切到看小顶堆。把 lo 的堆顶 7 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 7 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
平衡完成：共 8 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 5 + 🔻hi 顶 7) / 2 = 6。两个堆顶都在右侧面板里同时可见。
现在看大顶堆。第 9 个数 6 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 6 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 7。
切到看小顶堆。把 lo 的堆顶 6 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 6 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 5。
切回看大顶堆。小顶堆 hi 现在比 lo 多 1 个，违反「lo 至多比 hi 多 1」。把 hi 的堆顶 6 弹回 lo（橙色），两堆大小重新差 ≤ 1；此刻 lo 顶 = 6，hi 顶 = 7。
平衡完成：共 9 个数（奇数），🔺大顶堆 lo 比🔻小顶堆 hi 多 1 个，中位数就是 lo 的堆顶（绿色）= 6。此刻两堆顶：lo 顶 6、hi 顶 7，都列在右侧面板里。
现在看大顶堆。第 10 个数 10 先进大顶堆 lo（橙色）。上浮后 lo 的堆顶变成 10 —— 它是「较小一半」里最大的那个；另一侧小顶堆 hi 顶 = 7。
切到看小顶堆。把 lo 的堆顶 10 匀给小顶堆 hi（橙色）。这一步保证「lo 全部 ≤ hi 全部」，hi 的堆顶 7 是「较大一半」里最小的；另一侧大顶堆 lo 顶 = 6。
平衡完成：共 10 个数（偶数），两堆一样大，中位数 = 两个堆顶的平均 = (🔺lo 顶 6 + 🔻hi 顶 7) / 2 = 6.5。两个堆顶都在右侧面板里同时可见。
全部 10 个数加完（本侧画的是🔻小顶堆）。无论流多长，中位数永远夹在「🔺大顶堆顶 6」和「🔻小顶堆顶 7」之间，findMedian 只看这两个堆顶，O(1) 就能报出。
边界都靠「入堆 → 匀堆 → 平衡」三步自动维护，不必特判。
两个高频追问：推广到任意分位、海量数据流的近似方案。
参考代码
import heapqclass 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 # 偶数：两顶平均复杂度
- addNum：O(log n)，每次最多 3 次堆的 push/pop，每次 O(log n)
- findMedian：O(1)，只读两个堆顶，不做任何遍历
- 空间：O(n)，所有数分装在两个堆里
易错点
面试追问把动画讲成自己的话
追问如果要求第 k 百分位数（不是中位数），这套双堆还能用吗？
追问数据流非常大、内存放不下怎么办？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题