algorithm - 批量加载最小-最大堆

Question

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

虽然向上筛选和向下筛选是简单的修改，但棘手的部分是当元素需要从堆的最小有序部分移动到最大有序部分时。

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

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

Answer 1

我将用迄今为止所发现的内容来回答自己，以供其他可能有相同问题的人使用:

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

       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 个最大的，并以两层的步骤爬上树(即仅最小层)

或者我们可以查看大小为 7 的堆(3 层)并辨别最小和最大类型

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

确保对于最小级别我们有第一种类型，对于最大级别我们有第二种类型。然后我们需要完成所有级别。

但也许更好的解决方案是使用间隔堆。这本质上也是一个交错的最小和最大堆。然而，它们是对称交错的并且具有相同的大小。它们似乎更容易实现，并且可以解释为如下所示的堆:

      min1,max1
      /       \
min2,max2   min3,max3

有关批量加载的详细信息可以在原始间隔堆出版物中找到。

因此，如果您对可批量加载的最小最大堆感兴趣，请考虑查看区间堆! 有些人说无论如何它们的性能都优于最小最大堆；然而，它们密切相关，应该更容易实现。特别是，没有明显的理由说明为什么最小-最大堆应该表现更好，如果详细的复杂性分析表明它们在所需的比较和交换中表现更差，我不会感到惊讶(因为据我所知)可以天真地告诉，最小-最大堆需要更多的比较来验证堆的正确性)。