什么是 Min-Max Heap？它如何同时支持取最小值和最大值？

简化版

Min-Max Heap 是一种双端优先队列结构，既能快速取最小值，也能快速取最大值。

它按层交替维护最小层和最大层：最小层节点要小于其后代，最大层节点要大于其后代。根节点是最小值，最大值通常在根的两个孩子中。

它适合需要同时频繁删除最小值和最大值的场景，但实现复杂度高于普通堆。

详细版

普通小顶堆只能快速取最小值；普通大顶堆只能快速取最大值。

Min-Max Heap 用一个数组堆同时维护两端：

层级	约束
偶数层	Min 层，节点小于后代
奇数层	Max 层，节点大于后代

因此：

最小值在根节点；
最大值在根的孩子中；
插入和删除仍然是对数级。

level(index) = floor(log2(index + 1))

如果 level 是偶数，就按 Min 层规则调整；否则按 Max 层规则调整。

完整版教学

1. 为什么需要双端优先队列

普通优先队列只关注一端。

但有些场景需要同时支持：

查看最小值；
删除最小值；
查看最大值；
删除最大值。

例如实时数据窗口中既要剔除极大异常值，也要剔除极小异常值；或者调度系统既要拿最高优先级任务，也要清理最低优先级任务。

2. 用两个堆能不能做

可以用一个小顶堆和一个大顶堆，再配合懒删除。

这种方案工程上很常见：

结构	作用
小顶堆	取最小
大顶堆	取最大
哈希表	判断元素是否已经被另一边删除

Min-Max Heap 则试图用一个堆结构同时支持两端操作。

3. Min-Max Heap 的层级规则

Min-Max Heap 仍然是一棵完全二叉树，通常也用数组存储。

它的层级交替：

level 0: Min
level 1: Max
level 2: Min
level 3: Max

Min 层节点要小于它的所有后代，Max 层节点要大于它的所有后代。

它不是简单地左边小、右边大，而是按层维护最小约束和最大约束。

4. 为什么最小值在根，最大值在孩子

根节点位于 Min 层，并且要小于所有后代，所以根就是全局最小值。

根的两个孩子位于 Max 层。最大值不可能在更深的 Min 层绕过 Max 层祖先，因为 Max 层节点约束它大于后代。

因此全局最大值通常在根的两个孩子中，比较这两个孩子即可得到最大值。

如果元素数量小于 3，就按实际节点数处理边界。

5. 插入时如何调整

插入元素仍然先放到数组末尾。

然后判断它所在层：

如果在 Min 层，但比父节点大，可能应该去 Max 层路径调整；
如果在 Max 层，但比父节点小，可能应该去 Min 层路径调整；
否则在当前层按祖父节点方向上浮。

调整时常会和祖父节点比较，因为同类型层级隔一层出现一次。

6. 删除最小和删除最大怎么做

删除最小值就是删除根，类似普通堆从最后拿元素填根，再按 Min 层规则下沉。

删除最大值时，先找根的较大孩子，再删除该孩子，之后按 Max 层规则下沉。

操作	位置	调整方向
删除最小	根节点	Min 层下沉
删除最大	根的较大孩子	Max 层下沉

复杂度都是 O(log n)。

7. 和普通堆相比怎么评价

Min-Max Heap 的优势是一个结构同时支持双端优先队列。

缺点是实现更复杂，尤其是插入和下沉时要区分层级、父节点、祖父节点。

工程中，如果语言库没有现成实现，很多人会选择「双堆 + 懒删除」。

方案	优点	缺点
Min-Max Heap	单结构、双端操作	实现复杂
双堆懒删除	借助标准库	空间冗余、需清理过期

8. 常见误区与追问

误区：Min-Max Heap 是一个小顶堆加一个大顶堆。 它是单个完全二叉树结构，按层交替维护约束。
误区：最大值在数组最后。 最大值通常在根的两个孩子中，不是数组末尾。
误区：Min-Max Heap 比双堆方案总是更好。 双堆方案更容易用标准库实现，工程上反而更常见。
追问：为什么调整时常比较祖父节点？ 因为同类层级隔一层出现，Min 层向上还是 Min 层要跨过父节点到祖父节点。
追问：它适合什么场景？ 适合频繁同时取最小和最大，并且愿意维护专门结构的双端优先队列场景。

简化版

详细版