Bulk-loading a min-max heap

Question

A min-max heap is a heap that can find both the minimum and the maximum element in O(1) and remove it in O(log n). It is closely related to a classic heap, but it actually interleaves three heaps: a min-heap and two max-heaps, where even levels are min levels and odd levels are max levels (which thus have two roots). The classic heap properties hold with respect to grandchildren instead of children. The leaf level of the min-max-heap is essentially shared between the min and the max heaps, new elements inserted here can move both to even or to odd levels of the tree.

While the sift up and sift down are straightforward modifications, the tricky parts are when an elements needs to move from the min-ordered to the max-ordered part of the heap.

For a classic heap, I can bulk-load the tree in O(n) by performing a bottom up heap repair, while the obvious one-by-one insertion takes O(n log n) time. I can also do this for bulk insertions, instead of inserting them one by one I can append them all and the bulk-repair the heap.

For the min-max heap, I can of course linearly load it in O(n log n), but I wonder if there also is a way of bulk-loading it in O(n) or bulk-repairing the heap bottom-up?

Answer 1

I'm going to answer myself with what I found out so far, for others that may have the same question:

A min-max heap is essentially three heaps in one, with a shared leaf level.

       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

(Important note: this is not exact, as the heaps have a fan-out of 4! Plus, this is the logical order, not the memory layout, which interleaves the heaps level-wise) The objects at the leaf level belong to all three heaps, this is where elements transition from the min part to the max part of the heap.

Now one can compute the sizes of the min heap and max heap, use a partial sorting such as quickselect to partition the data and bulk load the three parts individually. However, quickselect already is about as expensive as you'd want the whole bulk-load to be (partially ordering the data set)! The other obvious way of bulk-loading and bulk-repairing (!) the heap is to look at smaller sub-heaps. In a regular min-heap, you would look at atomic heaps of three elements a,b,c and ensure that a is the smallest. Here we we can either look at heaps of the height 4, i.e. 15 elements:

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

And ensure that min1 is the smallest, max1 and max2 the two largest and m1-m4 the next 4 largest, and climb up the tree in steps of two levels (i.e. min levels only)

Or we can look at heaps of size 7 (3 levels) and discern min and max types

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

ensuring that for min levels we have the first type and for max levels we have the second type. We then need to go through all levels.

But maybe an even nicer solution is to go for interval heaps. This also is essentially an interleaved min and max heap. However, they are symmetrically interleaved and have the same size. They seem to be much simpler to implement, and can be interpreted as a heap looking like this:

      min1,max1
      /       \
min2,max2   min3,max3

Details on bulk-loading can be found in the original interval heap publication.

So if you are interested in a bulk-loadable min-max-heap, consider looking at interval heaps instead! Some people say they outperform min-max-heaps anyway; they are closely related and should be easier to implement. In particular, there is no obvious reason why a min-max-heap should perform better, and I would not be surprised if a detailed complexity analysis shows that they perform worse by a constant factor in comparisons and swaps needed (because as far as I can naively tell, a min-max-heap requires more comparisons to verify the heap correctness).

Answer 2

I believe bottom-up tree repair should work:

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)