Min-Max Heap：兼顾最小堆与最大堆的完全二叉树数据结构

在计算机科学中，最小-最大堆是一种完全二叉树数据结构，它结合了最小堆和最大堆的优点，即能够以常数时间检索、以对数时间删除其中的最小元素和最大元素。[2] 这使得最小-最大堆成为实现双端优先队列时非常有用的数据结构。与二叉最小堆和最大堆一样，最小-最大堆支持对数时间的插入和删除，并可以在线性时间内构建。[3] 最小-最大堆通常以数组形式隐式表示；[4] 因此它被称为隐式数据结构。

最小-最大堆的性质是：树中偶数层上的每个节点都小于其所有后代，而奇数层上的每个节点都大于其所有后代。[4]

该结构还可以推广到高效支持其他顺序统计操作，例如查找中位数、删除中位数，[2] find(k)（确定结构中第 k 小的值）以及操作 delete(k)（删除结构中第 k 小的值），对于任意固定的 k 值（或一组值）。后两个操作分别可以在常数时间和对数时间内实现。最小-最大序的概念可以扩展到其他基于最大序或最小序的结构，例如左偏树，从而生成一类新的（且更强大的）数据结构。[4] 最小-最大堆在实现外部快速排序时也很有用。[5]

最大-最小堆的定义方式类似；在这种堆中，最大值存储在根节点，最小值存储在根节点的某个子节点中。[4]

在以下操作中，我们假设最小-最大堆用数组 A[1..N] 表示；数组中的第 i 个位置对应位于堆中第 ⌊log₂i⌋ 层的节点。

创建最小-最大堆是通过改编 Floyd 的线性时间堆构建算法完成的，该算法以自底向上的方式进行。[4] 典型的 Floyd 建堆算法[6] 如下：

function FLOYD-BUILD-HEAP(h): for each index i from ⌊length(h)/2⌋ down to 1 do: push-down(h, i) return h

在这个函数中，h 是初始数组，其元素可能不满足最小-最大堆性质。接下来解释最小-最大堆的 push-down 操作（有时也称为 heapify）。

push-down 算法（在 [4] 中称为 trickle-down）如下：

function PUSH-DOWN(h, i): if i is on a min level then: PUSH-DOWN-MIN(h, i) else: PUSH-DOWN-MAX(h, i) endif

向下推入最小值 [编辑]

function PUSH-DOWN-MIN(h, i): if i has children then: m := index of the smallest child or grandchild of i if m is a grandchild of i then: if h[m] < h[i] then: swap h[m] and h[i] if h[m] > h[parent(m)] then: swap h[m] and h[parent(m)] endif PUSH-DOWN(h, m) endif else if h[m] < h[i] then: swap h[m] and h[i] endif endif

向下推入最大值 [编辑]

push-down-max 的算法与 push-down-min 完全相同，只是所有比较运算符都取反。

function PUSH-DOWN-MAX(h, i): if i has children then: m := index of the largest child or grandchild of i if m is a grandchild of i then: if h[m] > h[i] then: swap h[m] and h[i] if h[m] < h[parent(m)] then: swap h[m] and h[parent(m)] endif PUSH-DOWN(h, m) endif else if h[m] > h[i] then: swap h[m] and h[i] endif endif

迭代形式 [编辑]

由于 push-down-min 和 push-down-max 中的递归调用处于尾位置，这些函数可以简单地转换为纯迭代形式，在常数空间中执行：

function PUSH-DOWN-ITER(h, m): while m has children then: i := m if i is on a min level then: m := index of the smallest child or grandchild of i if h[m] < h[i] then: swap h[m] and h[i] if m is a grandchild of i then: if h[m] > h[parent(m)] then: swap h[m] and h[parent(m)] endif else break endif else break endif else: m := index of the largest child or grandchild of i if h[m] > h[i] then: swap h[m] and h[i] if m is a grandchild of i then: if h[m] < h[parent(m)] then: swap h[m] and h[parent(m)] endif else break endif else break endif endif endwhile

插入 [编辑]

要向最小-最大堆中添加元素，请执行以下操作：

该过程通过在新追加键的索引上调用下面描述的 push-up 算法来实现。

push-up 算法（在 [7] 中称为 bubble-up）如下：

function PUSH-UP(h, i): if i is not the root then: if i is on a min level then: if h[i] > h[parent(i)] then: swap h[i] and h[parent(i)] PUSH-UP-MAX(h, parent(i)) else: PUSH-UP-MIN(h, i) endif else: if h[i] < h[parent(i)] then: swap h[i] and h[parent(i)] PUSH-UP-MIN(h, parent(i)) else: PUSH-UP-MAX(h, i) endif endif endif

向上推入最小值 [编辑]

function PUSH-UP-MIN(h, i): if i has a grandparent and h[i] < h[grandparent(i)] then: swap h[i] and h[grandparent(i)] PUSH-UP-MIN(h, grandparent(i)) endif

向上推入最大值 [编辑]

与 push-down 操作一样，push-up-max 与 push-up-min 完全相同，只是比较运算符取反：

function PUSH-UP-MAX(h, i): if i has a grandparent and h[i] > h[grandparent(i)] then: swap h[i] and h[grandparent(i)] PUSH-UP-MAX(h, grandparent(i)) endif

迭代形式 [编辑]

由于对 push-up-min 和 push-up-max 的递归调用处于尾位置，这些函数也可以简单地转换为纯迭代形式，在常数空间中执行：

function PUSH-UP-MIN-ITER(h, i): while i has a grandparent and h[i] < h[grandparent(i)] then: swap h[i] and h[grandparent(i)] i := grandparent(i) endwhile

示例 [编辑]

下面是一个向最小-最大堆中插入元素的示例。

假设我们有如下最小-最大堆，并希望插入一个值为 6 的新节点。

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）