最小—最大堆

最小—最大堆（Min-Max Heap）是最大层和最小层交替出现的二叉树，即最大层结点的子节点属于最小层，最小层结点的子节点属于最大层。以最大（小）层结n点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。

最小—最大堆
类型	二叉树/堆
发明时间	1986
用大O符号表示的时间复杂度
算法 平均 最差 插入 O(log n) O(log n) 删除 O(log n) [1] O(log n)

完全最大堆示例

完全最小堆示例

介绍

最大堆和最小堆是二叉堆的两种形式。

• 最大堆：根结点的键值是所有堆结点键值中最大者的堆。
• 最小堆：根结点的键值是所有堆结点键值中最小者的堆。

而最大—最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。

应用

• 双端优先队列

参考文献

1. Mischel. Jim. Stack Overflow. [8 September 2016].