最大—最小堆

最小—最大堆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].