数据流的中位数

数一直在来，每问一次就重新排序，查得越频繁越崩。我们要的是「随时 O(1) 拿到中位数」，又不想每次重排——这正是要优化掉的浪费。

转折：中位数只跟「最中间那一两个数」有关，何必排好全部？用大顶堆 small 装较小一半（堆顶=这半的最大值）、小顶堆 large 装较大一半（堆顶=那半的最小值）。中位数永远卡在这两个堆顶上，拿它 O(1)。

维持两条规则：① small 里每个数 ≤ large 里每个数；② 本实现约定 small 的个数必须等于 large、或恰好比它多 1（即 len(small) − len(large) ∈ {0, 1}）。所以「small 多 2」或「large 比 small 多」都算失衡，要挪一个堆顶过去。奇数个时中位数 = small 堆顶；偶数个时 = 两堆顶平均。下面逐个加 5、3、8、1。

加入 5 · 放入：第一个数 5，放进左边大顶堆 small。两堆个数差 1，已平衡，不用挪。

加入 5 · 读中位数：一共 1 个数，奇数，中位数 = 数多的那个堆顶 = small 顶 5。

加入 3 · 放入（失衡）：加入 3：它比 small 顶 5 小，进左堆。但左堆一下多了 2 个、右堆空着——失衡了，下一步要调。

加入 3 · 平衡 + 读：平衡：把 small 堆顶 5 挪到 large。现在左 [3]、右 [5] 各一个。偶数个，中位数 = 两堆顶平均 = (3+5)/2 = 4。

加入 8 · 放入（失衡）：加入 8：比 large 顶 5 大，进右堆。这回右堆多了 1 个，又失衡——往多的一边的反方向挪。

加入 8 · 平衡 + 读：平衡：把 large 堆顶（最小的）5 挪回 small。左 [3,5]、右 [8]。奇数个，中位数 = 数多的 small 顶 5。

加入 1 · 放入（失衡）：加入 1：比 small 顶小，进左堆。左堆涨到 3 个，比右堆多 2——再调一次。

加入 1 · 平衡 + 读：平衡：small 顶 5 挪到 large。左 [1,3]、右 [5,8]。四个数排序是 1,3,5,8，中间两个 3、5，中位数 = (3+5)/2 = 4。全程没有重排，每步只挪一个堆顶。

「动态求中位数 / 求第 K 大」的经典结构：一个大顶堆 + 一个小顶堆对顶，维持大小平衡，中位数永远在两个堆顶之间。

边界三连：本题真边界：单数、偶数个、重复值。

面试官常追问：四个高频追问，对顶堆经典。