Min-Max Heaps and Double-Ended Extraction

A priority queue that must produce both the smallest and the largest element has an obvious implementation: two heaps over the same multiset, one ordered each way, with each element present in both. The cost is twice the memory and, worse, a synchronization problem — removing the minimum from the min-heap requires removing the same element from the max-heap, which means locating it there. A min-max heap avoids the duplication entirely by relaxing the heap property into an alternating pattern, so a single array answers both ends in constant time and removes either in logarithmic time.

Two levels of order in one array

The min-max heap is a complete binary tree in an array, exactly like a binary heap, with a different invariant. Nodes at even depth — the root at depth 0, its grandchildren at depth 2, and so on — are min levels. Nodes at odd depth are max levels. The property is stated in terms of nearest relatives of the same parity:

• A node on a min level is smaller than every element in its subtree.
• A node on a max level is larger than every element in its subtree.

Because levels alternate, the root is a min level and holds the global minimum, while its two children are max levels and each holds the maximum of its own subtree. The global maximum is therefore one of those two children — index 1 or index 2 — so find-max is a single comparison, and find-min reads index 0. Both are O(1), and both read from the same array with no duplication.

The invariant is easy to misstate, and the common misstatement is that each node is ordered only against its immediate parent. It is not. A min-level node is smaller than every node in its subtree, and a max-level node is larger than every node in its subtree. Ordering against the parent alone would not put the global maximum at the root’s children, because a max-level node’s children are min-level and could hold values larger than the parent if only the parent relation were constrained.

What the invariant does not say is anything about the ordering within a level. Two grandchildren of the root are both min-level nodes and are unrelated to each other; nothing in the structure records which is smaller. That silence is what keeps insertion and extraction logarithmic, and it is why the structure cannot answer a rank query such as “the third smallest element” without descending into subtrees.

This is also why the structure is not simply “a heap of heaps”. A plain binary heap would order each node against its children and, by transitivity, against its descendants; here the comparison is against descendants directly, but with the sense of the comparison alternating by depth. The repair routines must therefore decide, at each step, whether they are enforcing a min relation or a max one.

Two kinds of sift, and the case analysis

Insertion appends at the end and repairs upward. The repair is not a single sift-up, because the direction of the required comparison alternates with depth. At an even depth the new element sits on a min level and must be smaller than every element of its subtree, starting with its parent, which is on a max level; at an odd depth the senses reverse. The routine compares the new element with its parent first, since that is the nearest constraint; if the parent relation is violated, the two swap and the element continues upward from its parent’s slot. Once that relation holds, the element may still violate the grandparent, which is on the same parity level and therefore compared with the same sense; a single swap with the grandparent fixes it, and the repair ends, because the grandparent’s own relation to everything above it is unchanged by exchanging two elements that are both smaller (or both larger) than its parent.

Extraction of the minimum removes index 0 and moves the last element to the root. The repair must then push that element down through alternating levels. At a min level, the routine examines the element’s children and grandchildren, finds the smallest of them, and swaps it up. Two cases follow. If the smallest was a child, one swap restores the min relation at that level and the repair stops. If the smallest was a grandchild, the element takes the grandchild’s place two levels down — still a min level, since parity is preserved — and it may now exceed its new parent, a max-level node, which requires a second swap to fix that relation. The descent then continues from the grandchild’s original slot, where the swapped-up grandchild now sits, and the same two-case test repeats until the element settles.

/* Index of the most extreme descendant among the children and grandchildren of
   slot i (smallest on a min level, largest on a max level), or i if none. */
static size_t extreme_descendant(int *a, size_t n, size_t i, int want_min) {
    size_t cand[6] = { 2*i + 1, 2*i + 2,          /* children      */
                       4*i + 3, 4*i + 4,          /* of left child */
                       4*i + 5, 4*i + 6 };         /* of right child */
    size_t best = i;
    for (int j = 0; j < 6; j++) {
        size_t c = cand[j];
        /* c > i rejects the wrapped offsets of children that do not exist */
        if (c > i && c < n && (want_min ? a[c] < a[best] : a[c] > a[best])) best = c;
    }
    return best;
}

Given that index, the descent has exactly two cases. If the extreme is a child, one swap restores the level’s property and the descent stops, because the subtree below a child already satisfied the invariant. If the extreme is a grandchild, the swap puts the displaced element two levels down — the same level type, since parity is preserved — and that element may now be more extreme than its new parent, which is on the opposite level and therefore subject to the opposite comparison. One further comparison and swap fixes that relation, and the descent resumes from the grandchild’s slot, where the promoted grandchild now sits. That second phase is a plain sift-down within the same level type, so one descent costs at most two swaps at the level where the grandchild was promoted plus one per level it then falls, and the total is O(log n).

The candidate list is where implementations go wrong. A node with two children has six descendants within two levels, a node with one child has four, and a node with none has none. The guard c < n is not enough on its own: for a missing left child, 4*i + 3 wraps to a large value that can land back inside the array for some values of i, and c > i rejects those before the bound is read. Writing the loop over the six fixed offsets makes both conditions explicit; deriving the range from the child indices instead, as some sketches do, requires a parity test to exclude slots that are neither children nor grandchildren, and getting that wrong only shows up when the last level is partly filled.

Removing the maximum is symmetric but has one extra wrinkle. The maximum is at index 1 or 2, whichever is larger, so the routine must compare the two before it knows where the hole is. Removing it leaves a hole not at the root, so the standard trick of moving the last element there applies, but the repair must now start at a max level and push down accordingly, with the comparison directions inverted. The result is a routine structurally identical to the delete-min descent, differing only in whether it minimises or maximises at each comparison; a flipped sense flag captures that, which is how implementations usually write it.

What the layout buys and what it costs

The min-max heap’s advantage over the two-heap scheme is memory and consistency. A single array of n elements serves both ends, with no duplication and no cross-structure bookkeeping. Every operation maintains one structure, so there is no window in which the two views disagree. For a double-ended priority queue embedded in a larger system — an event scheduler that must cancel the earliest and the latest deadline — that consistency is worth more than the constant factor.

The cost is per-operation work. A binary heap’s sift-down performs two comparisons per level; the min-max version performs up to about six in the first step, because it must examine grandchildren as well as children, and two or three on each level after that. The height is the same, so the asymptotic bound is unchanged and the constant is several times larger. For extraction-heavy workloads, a plain binary heap with two parallel structures — one ordered each way, with the synchronization problem solved by lazy invalidation — can be faster despite the duplication.

A second cost is the case analysis. The correctness argument for the repair routines is a case split over (level parity) × (whether the extreme is a child or grandchild) × (whether the second swap is needed). Implementations that get one branch wrong produce a structure that passes a shallow invariant check and fails on specific input shapes. The published description of the structure devotes most of its length to these cases for exactly this reason.

A third is that the structure does not support decrease-key in the ordinary sense. Lowering an arbitrary element’s key requires the element’s position, and the repair direction depends on the parity of its level and on whether the change violates a min-level or max-level relation. The position map machinery described in indexed binary heaps applies unchanged, but the repair routine must compare against the grandparent as well as the parent, in either direction, so the single two-way sift of a binary heap becomes a case split it does not have.

Where the double-ended requirement comes from

The motivating applications are those where both extremes are meaningful. A scheduling system with deadlines needs the earliest deadline for dispatch and the latest for admission control. A branch-and- bound search needs the most promising node to expand and the least promising to prune. A sliding-window median needs to drop the oldest element from a window and read the median, which is a rank query rather than an extreme query — a related but different problem, solved by a pair of heaps with balancing rather than by a min-max heap.

The generalized form of the structure, described in the same 1986 paper, extends min-max ordering to other heap-ordered structures such as leftist trees, and derives order-statistic operations from it — constant-time FindMin, FindMax, and FindMedian, with the corresponding deletions in logarithmic time. The two-level min-max heap is the case that carries two extremes, which is the requirement most systems actually have.

For the specific case of “minimum and maximum, with removal of either”, there is a simpler alternative worth knowing: keep a binary heap of the smaller half and a binary heap of the larger half, rebalancing so the two differ in size by at most one. That arrangement gives constant-time access to both extremes and logarithmic removal, with two arrays instead of one and a rebalancing step. The min-max heap’s argument is that one array and one invariant is easier to reason about; the two-heap argument is that each heap is the structure from array layout and sift with no new case analysis, so the code is already understood.

The choice between them turns on how much the extra comparisons cost relative to the extra memory. For small elements and moderate n, both fit in cache and the min-max heap’s larger constant is the dominant term. For large elements and large n, the duplicated storage in the two-heap scheme costs more cache traffic than the extra comparisons, and the min-max layout wins. Neither structure dominates the other on asymptotics; the decision is a constant-factor one that follows from element width.