滑动窗口中位数为什么常用双堆加延迟删除？

简化版

滑动窗口中位数需要同时支持插入新元素、删除过期元素、查询中位数。

双堆可以维护较小一半和较大一半：大顶堆保存较小一半，小顶堆保存较大一半。但普通堆不支持高效删除任意过期元素，所以常配合延迟删除表。

当过期元素跑到堆顶时，再真正弹出它。

详细版

双堆求中位数的核心是不变量：

small 是大顶堆，保存较小的一半；
large 是小顶堆，保存较大的一半；
两个堆大小差不超过 1；
中位数由堆顶决定。

滑动窗口比普通数据流中位数多了一个删除操作。由于堆无法快速删除内部元素，所以会用 delayed 哈希表记录某个值需要被删除几次。

remove(x):
  delayed[x] += 1
  如果 x 属于 small，smallSize--
  否则 largeSize--
  prune(heap)
  rebalance()

prune 的作用是：只要堆顶元素已经标记过期，就弹出。

完整版教学

1. 普通数据流中位数为什么用双堆

中位数要求把数据分成左右两半。

如果有序数组维护中位数，查询很快，但插入可能要移动元素，成本高。

双堆的做法是：

堆	保存内容	堆顶含义
`small` 大顶堆	较小的一半	左半部分最大值
`large` 小顶堆	较大的一半	右半部分最小值

当元素总数为奇数时，可以让 small 多 1 个元素，中位数就是 small.peek()。

2. 滑动窗口多出来的难点

滑动窗口每向右移动一步，会发生两件事：

加入一个新元素；
移除一个离开窗口的旧元素。

插入新元素适合堆，但删除旧元素不一定是堆顶。

比如旧元素在堆内部，普通堆没有它的位置，只能线性扫描。为了避免 O(k) 删除，常用延迟删除。

延迟删除的本质是：先记账，等元素到堆顶时再真正清理。

3. delayed 表保存什么

delayed 通常是一个哈希表：

delayed[value] = 这个 value 还需要被删除的次数

如果窗口里有重复元素，计数就很重要。不能只用 set，否则两个相同值会被误删。

例如：

窗口移出 5 一次:
delayed[5] += 1

当某个堆的堆顶是 5 时：

while heap.peek() in delayed:
  delayed[heap.peek()] -= 1
  heap.pop()

计数归零后再删除 key。

4. 为什么还要维护有效大小

堆数组里可能残留过期元素，所以 heap.length 不等于有效元素数量。

因此通常维护两个变量：

smallSize：大顶堆有效元素个数；
largeSize：小顶堆有效元素个数。

这两个值用于判断是否需要 rebalance。

指标	是否包含过期元素
堆数组长度	包含
有效大小变量	不包含

如果不维护有效大小，平衡逻辑会被过期元素干扰。

5. 如何判断删除元素属于哪个堆

删除元素 x 时，通常用 x <= small.peek() 判断它属于左半边，否则属于右半边。

然后减少对应有效大小：

if x <= small.peek():
  smallSize--
else:
  largeSize--

这个判断基于双堆不变量：左半边元素都不大于右半边元素。

6. rebalance 做什么

rebalance 要保证两个堆大小关系合理。

常见规则：

如果 smallSize > largeSize + 1，把 small 堆顶移到 large。
如果 smallSize < largeSize，把 large 堆顶移到 small。

移动前后都要 prune，避免把过期堆顶当作有效元素。

rebalance():
  if smallSize > largeSize + 1:
    large.push(small.pop())
    smallSize--
    largeSize++
    prune(small)

7. 复杂度怎么分析

窗口大小为 k，数组长度为 n。

每个元素最多：

入堆一次；
被真正弹出一次；
在 delayed 表里记账一次。

所以整体复杂度通常回答：

操作	复杂度
每次滑动	`O(log k)` 摊还
查询中位数	`O(1)`
总时间	`O(n log k)`
空间	`O(k)`

8. 常见误区与追问

误区：延迟删除可以不处理重复值。 必须用计数，否则相同值会被误删。
误区：堆的数组长度就是有效大小。 延迟删除会让堆里残留过期元素，必须维护有效大小。
误区：移出元素时必须立刻从堆里删掉。 立刻删除可能退化为线性扫描，延迟到堆顶再删更高效。
追问：为什么不用一个平衡树？ 平衡树也可以，删除任意元素更自然；双堆适合语言有优先队列但没有好用多重有序集合的场景。
追问：中位数是两个堆顶平均时要注意什么？ 整数溢出和浮点精度都要注意，可以先转成更大范围类型再相加。

简化版

详细版