双堆结构实现滑动窗口中位数维护

滑动窗口中位数问题的真正挑战不在于计算中位数本身，而在于窗口动态滑动时如何高效、精准地完成“删旧+加新”操作——双堆（大根堆+小根堆）虽是主流解法，但成败关键全在细节：左堆存较小半、右堆存较大半，通过维护长度差dif实现奇偶k下的动态平衡；插入与删除必须联动更新dif而非孤立操作；延迟删除必须严格遵循“先清左堆、再清右堆”的顺序，否则堆顶失效将导致整个平衡逻辑雪崩；再加上Python模拟大根堆的负值陷阱、k=1时空右堆防护、初始化平分误区等边界坑点，稍有疏忽中位数就会系统性偏移——这是一场对数据结构直觉与工程严谨性双重考验的精密平衡术。

滑动窗口中位数的核心难点不在“求中位数”，而在“窗口滑动时高效删旧加新”。双堆结构（大根堆 + 小根堆）是主流解法，但真正卡住多数人的，是动态平衡的细节和延迟删除的落地——不是堆建不对，而是平衡逻辑一错，中位数就全偏了。

堆的角色与基本平衡规则

左堆（大根堆）存较小的一半，右堆（小根堆）存较大的一半。关键不是“两堆数量相等”，而是始终满足：
– 若窗口大小 k 为奇数：左堆比右堆多 1 个元素；
– 若 k 为偶数：两堆元素数量相等。
这决定了中位数直接由堆顶给出：
• 左堆元素更多 → 中位数 = 左堆堆顶（取负）；
• 两堆相等 → 中位数 = (左堆堆顶 + 右堆堆顶) / 2。

插入与删除不能分开想，必须联动计算差值

每次窗口右移，实质是一删一加。重点在于：不立即物理删除旧数，而是用 延迟删除 + 差值追踪 来简化逻辑：

• 维护一个变量 dif = len(左堆) − len(右堆)，初始按 k 奇偶设为 1 或 0
• 删 num_out：
  　　若 num_out ≤ 左堆堆顶 → 它属于左堆 → dif 减 1；
  　　否则属于右堆 → dif 加 1
• 加 num_in：
  　　若 num_in ≤ 左堆堆顶 → 加入左堆 → dif 加 1；
  　　否则加入右堆 → dif 减 1
• 最终 dif 只可能是 −2、0、+2：
  　　dif == 2 → 左堆多出 2 个 → 把左堆堆顶移到右堆；
  　　dif == −2 → 右堆多出 2 个 → 把右堆堆顶移到左堆

延迟删除必须“先清左、再清右”

延迟删除靠哈希表记录待删次数，但清理堆顶无效元素有顺序要求：

• 每次取中位数前，先检查左堆堆顶是否已被标记删除；是则弹出并更新计数，直到堆顶合法
• 再检查右堆堆顶；同样弹出至堆顶有效
• 务必先清左堆——因为中位数优先依赖左堆堆顶，若它无效却没清理，后续所有 dif 判断和移动都会错位
• 清理操作只在 getMedian() 和 balance() 前执行，不每步都扫全堆，避免冗余开销

边界与类型处理不能靠猜测

实际编码中几个易漏点：

• Python 没有原生大根堆，用 heapq 堆存负值 模拟，所有取堆顶、比较、插入都要统一加/减负号，建议封装成 get_left_top() 方法避免出错
• 窗口初始化阶段，前 k 个数不能直接平分：先全塞左堆，再把最大的 ⌊k/2⌋ 个逐个移到右堆，确保初始状态符合 dif 规则
• 当 k == 1 时，dif 始终为 1，右堆恒为空，代码中需防空堆访问（如不判断 right[0] 就引用会报错）
• 浮点精度：题目允许误差 ≤ 1e−5，但 Python 中整数除法用 / 即可，无需手动转 float

本篇关于《双堆结构实现滑动窗口中位数维护》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！