对顶堆·中位数

10 分钟

动态求中位数用两个堆:大根堆存较小的一半,小根堆存较大的一半,保持两堆大小差 <=1。中位数就在堆顶附近。每次插入后调整两堆平衡即可。

小纸条

两堆元素总数为奇数时,中位数在哪个堆顶?

登录 后可看答案

对顶堆·中位数 · 算法进阶 · op599 课程