第6章｜二分、堆与优先队列

Unit 11 · LeetCode #295 · 状态依赖训练版

← Unit 10 仅本次页面有效
295
Median from Data StreamTwo Heaps · Balance · Stream
已恢复上次学习位置

一个堆暴露一条边界，
两个堆共同夹住动态中位数。

左侧最大堆保存较小一半，右侧最小堆保存较大一半。只要所有左侧值不大于右侧值，并让左堆与右堆大小相等或多一个，中位数就只依赖两个堆顶。

LeetCode #295 原题内容题面转述、设计接口与复杂度

题目要求

中位数是有序整数列表的中间值。若列表长度为偶数，则中位数是两个中间值的平均数。

实现 MedianFinder：addNum(num) 向数据流加入整数，findMedian() 返回目前所有元素的中位数。

class MedianFinder: def __init__(self): pass def addNum(self, num: int) -> None: pass def findMedian(self) -> float: pass

约束

  • -10⁵ ≤ num ≤ 10⁵；
  • 调用 findMedian 前至少已有一个元素；
  • addNum 与 findMedian 总调用次数最多 5×10⁴。

官方示例

MedianFinder()
addNum(1)
addNum(2)
findMedian() → 1.5
addNum(3)
findMedian() → 2.0

中位数定义

[2,3,4] → 3
[2,3] → (2+3)/2 = 2.5

本页主方法

左侧使用最大堆、右侧使用最小堆。每次插入为 O(log n)，查询中位数为 O(1)，总空间为 O(n)。

Lower Half

较小的一半数据。概念上使用最大堆，使左半最大值始终位于堆顶；Python以负数模拟。

Upper Half

较大的一半数据。使用最小堆，使右半最小值始终位于堆顶。

跨堆有序性

左堆所有真实值均不大于右堆所有值，因此两个堆顶正好位于排序中心两侧。

大小平衡

本页约定左堆大小等于右堆，或仅多一个；奇数中位数因此位于左堆顶。

1. 奇偶中位数与中心边界
2. 左最大堆与右最小堆
3. 插入、跨堆移动与再平衡
4. 不变量、范围优化与错误实验
5. Python与完整数据流轨迹
6. 滑动窗口中位数迁移
教学数据流：[5,2,10,4,3,8]观察排序中心如何移动
Lower Half｜最大堆｜较小一半
Upper Half｜最小堆｜较大一半

左侧概念最大堆 / Python负数堆

右侧最小堆

左堆大小0
⚖
右堆大小0
len(lower) == len(upper) 或 len(lower) == len(upper) + 1
尚未加入数据。
当前中位数证据

中位数由有序数据中心的一个或两个边界值决定。

双堆联合不变量 max(lower) ≤ min(upper)，且左堆与右堆等大或左堆多一个。
加入后数据左堆顶右堆顶中位数

插入与平衡记录

当前新值—
左堆真实堆顶—
右堆堆顶—
当前中位数—

顺序不变量

左堆中的每个真实值都不大于右堆中的每个值；两个堆顶因此是排序中心附近的边界。

大小不变量

左堆与右堆等大时取两个堆顶平均；左堆多一个时直接取左堆顶。

已加入元素数0
左堆大小0
右堆大小0
大小差0
当前中位数—
完整排序维护所有顺序，双堆只维护中心两侧边界

每次重新排序成本高；有序数组插入需要移动元素；双堆以O(log n)增量更新中心边界，并以O(1)读取中位数。

只有“两个堆大小接近”仍然不够

双堆必须同时满足顺序和大小两个不变量；任何一个被破坏，中位数都会失去含义。

错误一：只按大小随便分堆

即使两个堆数量相等，若左堆含10而右堆含2，两个堆顶并不代表排序中心。

错误二：忘记负号

Python左堆保存负数；真实左堆顶是 -lower[0]，不能直接使用lower[0]。

错误三：允许大小差超过1

中心位置会落在较大堆内部而不一定在堆顶，O(1)查询失效。

官方范围追问可以用计数数组进一步优化

若所有数都在[0,100]，可维护101个频率计数并扫描累计频率定位中心；若99%位于该范围，可对区间内计数并单独维护少量区间外数据。

重复值
可同时出现在两个堆
不影响边界定义
负数
左堆仍用负号模拟
注意双重符号
[0,100]有限范围
计数数组空间O(1)
查询扫描101格
补全LeetCode提交代码左堆承担奇数时的额外元素
class MedianFinder:
def __init__(self):
self.lower = [] # negatives
self.upper = []
def addNum(self, num):
moved =
if len(self.upper) > len(self.lower):
moved_back =
def findMedian(self):
if len(self.lower) > len(self.upper):
return
return
提示会逐层解释“顺序修复 → 大小修复 → 奇偶读取”，不会提供完整实现。
为什么“先左、再把左最大值移到右、必要时移回”有效？ 第一步允许新值暂时进入lower；把lower最大真实值移动到upper后，能保证lower中的所有值≤upper中的所有值。若upper因此多一个，再把upper最小值移回lower，使lower承担奇数时的额外元素。 也可以先判断num≤-lower[0]放入对应堆，再根据大小差进行平衡；两种写法维护的是同一组不变量。
代码—排序带—双堆顶—平衡秤联动数据流5,2,10,4,3,8
1class MedianFinder:
2 def __init__(self):
3 self.lower = []
4 self.upper = []
6 def addNum(self, num):
7 heappush(lower, -num)
8 moved = -heappop(lower)
9 heappush(upper, moved)
11 if len(upper) > len(lower):
12 moved_back = heappop(upper)
13 heappush(lower, -moved_back)
16 if len(lower) > len(upper):
17 return -lower[0]
19 return (-lower[0] + upper[0]) / 2
每个新值都经历“进入lower→lower最大值转移到upper→必要时upper最小值移回lower”，随后立即读取中位数。
完成代码联动后进入滑动窗口删除迁移主代码全部正确，或完整播放双堆轨迹后解锁。

迁移题：LeetCode #480 滑动窗口中位数

在 #295 的双堆基础上增加“旧值离开窗口”。堆无法高效删除任意内部元素，因此需要延迟删除、有效元素计数和堆顶清理。

打开 LeetCode 官方原题 ↗
1. 官方读题
2. 结构排序
3. 语义槽位
4. 样例与重写

官方任务

给定整数数组 nums 和窗口大小 k。窗口每次向右移动一格，返回每个窗口的中位数。

nums = [1,3,-1,-3,5,3,6,7]
k = 3
输出 = [1,-1,-1,3,5,6]

新增困难

  • 每一步都加入一个新值。
  • 除第一个窗口外，还要删除一个离窗旧值。
  • 堆只能高效弹出根，不能直接删除内部任意元素。
  • 答案误差在 10^-5 内可接受；1 ≤ k ≤ n ≤ 10^5。
第一个窗口 [1,3,-1] 的中位数是什么？
窗口右移时，相比 #295 新增了哪项状态变化？

#295 → #480 结构对照

#295 持续数据流
操作：只 add
大小：物理堆大小 = 有效大小
过期值：不存在
查询：读取两个有效堆顶
#480 固定窗口
操作：add + remove
大小：必须维护逻辑有效大小
过期值：delayed[value] 记账
查询：先 prune，再读堆顶

按依赖关系排列一次窗口右移

尚未选择步骤。
槽位 1｜删除记账
槽位 2｜prune 的触发条件
槽位 3｜有效大小
槽位 4｜查询前条件

官方样例窗口

物理堆、逻辑大小与延迟删除

lower 物理内容（真实值）
upper 物理内容
delayed 账本
关键观察

完整运行六个窗口后开放独立编辑器。

第6章 Unit 11 Skill卡

动态中位数需要同时维护排序中心两侧：左最大堆提供较小一半的最大值，右最小堆提供较大一半的最小值；顺序不变量决定边界正确，大小不变量决定中位数只需O(1)读取。

题号与题型#295｜双堆动态中位数
左侧结构最大堆保存较小一半，Python存负数
右侧结构最小堆保存较大一半
顺序不变量max(lower)≤min(upper)
大小不变量|lower|=|upper|或|lower|=|upper|+1
奇偶查询奇数取左顶；偶数取两顶平均
复杂度addNum O(log n)，findMedian O(1)，空间O(n)
常见错误只平衡大小；左堆忘记负号；大小差超过1
推荐迁移#480 滑动窗口中位数：双堆＋延迟删除

完成本单元后，你应能：

用顺序与大小两个不变量解释双堆
区分物理堆长度与逻辑有效大小
独立完成 #480 延迟删除实现