如何求数据流的中位数？（对顶堆）

简化版

用两个堆「对顶」：一个大顶堆存较小的一半、一个小顶堆存较大的一半，让大顶堆的堆顶（较小半的最大值）和小顶堆的堆顶（较大半的最小值）在中间「顶」着。保持两堆元素个数相等或只差 1。取中位数：两堆一样多时取两个堆顶的平均，否则取元素多的那个堆的堆顶。插入 O(log n)、取中位数 O(1)。

详细版

大顶堆 left：存较小的一半，堆顶是这半里的最大值。
小顶堆 right：存较大的一半，堆顶是这半里的最小值。
不变式：left 所有元素 ≤ right 所有元素，且 |left.size - right.size| ≤ 1。

PriorityQueue<Integer> left  = new PriorityQueue<>(Collections.reverseOrder()); // 大顶堆
PriorityQueue<Integer> right = new PriorityQueue<>();                           // 小顶堆

void addNum(int num) {
    left.offer(num);              // 先进大顶堆
    right.offer(left.poll());     // 把大顶堆最大的挪给小顶堆（保证 left≤right）
    if (right.size() > left.size())
        left.offer(right.poll()); // 平衡大小，让 left 多或相等
}
double findMedian() {
    if (left.size() > right.size()) return left.peek();          // 奇数个，中间在 left
    return (left.peek() + right.peek()) / 2.0;                   // 偶数个，取两堆顶平均
}

完整版教学

一、为什么用「对顶堆」

中位数是「一批数排序后正中间的数」。难点在于数据流不断进来、还要随时能报出中位数——每次都排序太慢（O(n log n)）。观察：中位数只和「中间那一两个数」有关，我们并不需要整体有序，只需要把数据劈成两半，随时能拿到「较小半的最大值」和「较大半的最小值」。

「拿一半里的最大/最小值」正是堆的强项。于是用两个堆对着放：大顶堆管较小的一半（顶部是它的最大值）、小顶堆管较大的一半（顶部是它的最小值），两个堆顶在中间「对顶」，中位数就在这两个堆顶之间。

二、两个不变式

要让这套结构正确，始终维持两条不变式：

划分正确：left（大顶堆，较小半）的每个元素都 ≤ right（小顶堆，较大半）的每个元素。这样中位数一定落在两个堆顶附近。
大小平衡：两堆元素个数相等，或相差 1。这样才能保证堆顶就是中位数位置。

每次插入后都要通过「倒腾元素」维持这两条。

三、插入的标准套路

一个不易出错的插入写法（保证 left ≤ right 且 left 的个数 ≥ right）：

新元素先进 left（大顶堆）。
把 left 的堆顶（当前较小半的最大值）弹出，塞进 right——这一步保证「left 的所有元素 ≤ right」（因为刚把 left 最大的移过去了）。
如果 right 比 left 还多，就把 right 的堆顶弹回 left，维持大小平衡（让 left 与 right 相等或多 1）。

这样走一遍，两条不变式都自动维持。

四、取中位数

总数为奇数：两堆大小差 1，中位数就是较多的那个堆的堆顶（上面的写法里是 left）。
总数为偶数：两堆一样大，中位数是两个堆顶的平均值 (left.peek() + right.peek()) / 2.0。

取中位数只是读堆顶，O(1)。

五、复杂度与延伸

插入 addNum：O(log n)（几次堆的插入/弹出）。
查询 findMedian：O(1)。
延伸——滑动窗口中位数：窗口滑动时要从堆里删除离开窗口的元素，普通堆删任意元素是 O(n)。可用「延迟删除（懒删除）」+ 哈希表标记，或用 TreeMap/有序多重集合来支持删除。这是本题的进阶版。

六、常见误区与追问

考点	正确口径
小的一半	用大顶堆保存，堆顶是较小半边最大值
大的一半	用小顶堆保存，堆顶是较大半边最小值
平衡规则	两个堆大小差不超过 1

maxHeap.size == minHeap.size:
  median = (maxHeap.peek + minHeap.peek) / 2
else:
  median = biggerHeap.peek

对顶堆维护的是中位数两侧的边界，不需要让所有数据整体有序。

误区：每次都排序才能取中位数。 数据流场景排序成本高，对顶堆只维护两半边界即可。
误区：两个堆大小可以相差很多。 大小差超过 1 时中位数位置会偏移，必须通过搬移堆顶重新平衡。
误区：大顶堆里可以有比小顶堆更大的元素。 必须保证大顶堆所有元素不大于小顶堆元素，否则边界错乱。
追问：插入一个数的标准流程是什么？ 先放入某一堆，再按大小边界和堆大小做调整，保证两个不变式。
追问：偶数个元素中位数怎么算？ 取两个堆顶平均值，注意整数溢出和浮点返回类型。
追问：复杂度是多少？ 插入需要堆操作 O(log n)，查询中位数只看堆顶 O(1)。

七、加强记忆

数据流中位数用对顶堆：大顶堆存较小一半（顶=较小半最大值）+ 小顶堆存较大一半（顶=较大半最小值），两堆顶在中间对顶。维持两不变式：left 全部 ≤ right、两堆大小差 ≤ 1。插入套路「进 left → 把 left 堆顶移给 right → 若 right 更多则移回」。取中位数：奇数取较多堆的堆顶、偶数取两堆顶平均，插入 O(log n)、查询 O(1)。滑动窗口版需支持删除（懒删除）。

简化版

详细版