数据流的中位数
一、问题背景与核心挑战
在实时统计、日志分析等场景中，我们经常需要处理动态数据流，并实时计算其中位数。中位数的定义是：
- 若序列长度为奇数，中位数是有序序列的中间值；
- 若序列长度为偶数，中位数是中间两个值的平均值。
如果每次添加元素后都重新排序，时间复杂度为 O(n log n)，当数据流规模很大时，这种方法无法满足实时性要求。因此，我们需要一种更高效的方式来动态维护中位数。
二、核心思路：双堆法（大顶堆 + 小顶堆）
为了高效维护中位数，我们可以用两个堆分别存储数据流的前半部分和后半部分：
| 堆类型 | 存储内容 | 堆顶含义 |
|---|---|---|
| 大顶堆（max-heap） | 数据流中较小的一半元素 | 较小一半的最大值 |
| 小顶堆（min-heap） | 数据流中较大的一半元素 | 较大一半的最小值 |
通过这两个堆的堆顶，我们可以快速计算中位数：
- 若元素总数为奇数：大顶堆的堆顶就是中位数（大顶堆比小顶堆多 1 个元素）；
- 若元素总数为偶数：中位数是大顶堆堆顶与小顶堆堆顶的平均值。
关键性质（必须满足）
- 大小关系：大顶堆的大小要么等于小顶堆，要么比小顶堆大 1；
- 元素关系：大顶堆中所有元素 ≤ 小顶堆中所有元素。
这两个性质保证了中位数的位置正确，且计算高效。
三、操作步骤详解
1. 初始化两个堆
- 大顶堆：用
PriorityQueue实现，通过Collections.reverseOrder()反转比较器，使其成为大顶堆； - 小顶堆：用默认的
PriorityQueue（Java 中默认是小顶堆）。
private PriorityQueue<Integer> maxHeap; // 大顶堆，存较小的一半
private PriorityQueue<Integer> minHeap; // 小顶堆，存较大的一半
public MedianFinder() {
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
2. 添加元素（addNum）
当新元素 num 到来时：
- 判断归属：若大顶堆为空，或
num <= maxHeap.peek()，则将num加入大顶堆；否则加入小顶堆；
