2

最小-最大堆是可以在 中找到最小和最大元素O(1) 并将其删除的堆O(log n)。它与经典堆密切相关，但它实际上交错了三个堆：一个最小堆和两个最大堆，其中偶数级别是最小级别，奇数级别是最大级别（因此有两个根）。经典的堆属性适用于孙子而不是孩子。min-max-heap 的叶子层级本质上在 min 和 max 堆之间共享，在这里插入的新元素可以移动到树的偶数层或奇数层。

虽然 sift up 和 sift down 是简单的修改，但棘手的部分是当元素需要从堆的最小排序部分移动到最大排序部分时。

对于经典堆，我可以O(n)通过执行自下而上的堆修复来批量加载树，而明显的逐一插入需要O(n log n)时间。我也可以为批量插入执行此操作，而不是一一插入，我可以将它们全部附加并批量修复堆。

对于 min-max 堆，我当然可以线性加载它O(n log n)，但我想知道是否还有一种方法可以将它批量加载O(n)或批量修复堆自下而上？

4

2 回答 2

2

对于可能有相同问题的其他人，我将用我迄今为止发现的内容来回答自己：

最小-最大堆本质上是三合一的堆，具有共享的叶级别。

       min1           <--- one min heap, first level
     /      \
   mi2       mi3      <--- third level
  /   \     /   \
 m5   m6   m7   m8    <--- fifth level
 /\   /\   /\   /\
a  b c  d e  f g  h   <--- leaf level (here: sixth level)
 \/   \/   \/   \/
 x1   x2   x3   x4    <--- fourth level
   \ /       \ /
   max1      max2     <--- two max heaps, second level

（重要提示：这不准确，因为堆的扇出为 4！另外，这是逻辑顺序，而不是内存布局，它按层次交错堆）叶级别的对象属于所有三个堆，这是元素从堆的最小部分过渡到最大部分的地方。

现在可以计算最小堆和最大堆的大小，使用部分排序（例如快速选择）对数据进行分区并单独批量加载这三个部分。但是，quickselect 的成本已经与您希望整个批量加载的成本一样高（部分订购数据集）！批量加载和批量修复（！）堆的另一种明显方法是查看较小的子堆。在常规最小堆中，您将查看三个元素 a、b、c 的原子堆，并确保 a 是最小的。在这里，我们可以查看高度为 4 的堆，即 15 个元素：

         min1
         /  \
    max1      max2
   /  \        /  \
 m1    m2    m3    m4
 /\    /\    /\    /\
a  b  c  d  e  f  g  h

并确保 min1 是最小的，max1 和 max2 是最大的两个，m1-m4 是接下来的 4 个最大的，并且分两级爬上树（即仅 min 级）

或者我们可以查看大小为 7（3 个级别）的堆并识别最小和最大类型

   min1           max1
   /  \           /  \
max1  max2     min1  min2
 /\    /\       /\    /\
a  b  c  d     a  b  c  d

确保对于最低级别我们有第一种类型，对于最高级别我们有第二种类型。然后我们需要遍历所有级别。

但也许更好的解决方案是使用区间堆。这本质上也是一个交错的最小和最大堆。但是，它们是对称交错的并且具有相同的大小。它们似乎实现起来要简单得多，并且可以解释为如下所示的堆：

      min1,max1
      /       \
min2,max2   min3,max3

有关批量加载的详细信息，请参阅原始区间堆出版物。

因此，如果您对可批量加载的最小最大堆感兴趣，请考虑查看区间堆！有人说它们无论如何都优于最小最大堆；它们密切相关，应该更容易实施。特别是，没有明显的理由为什么最小最大堆应该表现得更好，如果详细的复杂性分析表明它们在需要的比较和交换中的一个常数因子表现更差（因为据我可以天真地说，一个 min-max-heap 需要更多的比较来验证堆的正确性）。

于 2012-07-29T16:44:15.750 回答
0

我相信自下而上的树修复应该有效：

def heapify(N)
  if (N is a min-node)
     if(*N > *left_child(N))
        swap(*N, *left_child(N))
     if(*N > right_child(N))
        swap(*N, *right_child(N))
     find the smallest X among N, grand-children(N)
  else
     if(*N < left_child(N))
        swap(*N, *left_child(N))
     if(*N < right_child(N))
        swap(*N, *right_child(N))
     find the largest X among N, grand-children(N)
  if(X != N)
     swap(*X, *N)
     heapify(X)

load heap in arbitrary order
for each N in bottom-up order of heap
   heapify(N)
于 2012-07-25T10:37:31.317 回答