批量加载最小-最大堆

我将用我迄今为止的发现来回答自己,对于其他可能有同样问题的人来说:

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

       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)对数据进行分区,并分别大容量加载这三个部分。然而 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

有关大容量加载的详细信息可以在原始间隔堆发布中找到。

因此,如果您对批量可加载的最小-最大堆感兴趣,请考虑查看间隔堆! 有些人说,无论如何,它们的表现都优于最小-最大堆;它们密切相关,应该更容易实现。特别是,没有明显的理由说明最小-最大堆应该表现得更好,如果详细的复杂性分析显示,在所需的比较和交换中,它们的表现更差是一个恒定的因素,我也不会感到惊讶(因为据我所知,最小-最大堆栈需要更多的比较来验证堆的正确性)。

我认为自下而上的树木修复应该奏效:

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)