algo/di-yi-zhan-da78c/shou-ba-sh-daeca/yi-dao-qiu-b3109/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-daeca/yi-dao-qiu-b3109/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员，新版刷题打卡挑战 (https://labuladong.gitee.io/algo/challenge/) 上线！ 读完本文，你不仅学会了算法套路，还...

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-daeca/yi-dao-qiu-b3109/

[shiboys]

「如果插入的 num 大于 small 的堆顶元素，那么 num 就会成为 samll 的堆顶元素，最后还是会被插入 large 堆中」这句话不甚理解！
感觉还是 剑指 Offer 解释的更清楚些，会跟大小堆顶的元素进行比较

[leoZheng0]

你这样想,假设现在small的元素比large少一个,而且算法必须要保证large里面的所有人都比small里面的人小,所以这一轮无论如何都要给small加一个元素,否则破坏平衡.
那么有两种情况:我要插入num
1.num<small的堆顶元素,意味着num比small的所有人都要小,那我直接插入到large堆中没有问题
2.num>small的堆顶元素,意味着起码有一个small堆里面的人比他大,那么根据上面说的我要保证large里面的所有人都比small里面的人小,我必须把num插入large当中,但是此时small的元素就比large的元素少了2个,不平衡了,作为补偿,我要把small里面的最小值给到large,也就是poll给它

综上所述,无论怎样num跟small的堆顶元素是什么关系,我们都可以通过"先将num插入small,再将small的堆顶元素给到large"这个操作来做到正确的插入一个元素.