Weak Heap

A weak heap is an implicit, array-backed priority queue data structure within computation and algorithms that relaxes the structural and ordering invariants of a classical binary heap by encoding a half-ordered binary tree (isomorphic to a heap-ordered binomial tree) inside an array A[0 .. n − 1] augmented with an auxiliary bit vector r[0 .. n − 1] of n reversal bits. Introduced by Ronald D. Dutton in 1993 in BIT Numerical Mathematics and later extended to full priority queues and index-only navigation by Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen (2012, 2013), the weak heap eliminates the left-subtree ordering constraint of standard binary heaps: the root at A[0] has no left child, and every node's key is required to be greater than or equal to (in a max-weak heap) only the keys in its right subtree.

Because a node in a weak heap is unrelated in order to its left subtree, restoring the weak-heap invariant along the right spine of the root's child requires only 1 key comparison per tree level (via a constant-time pairwise join operation that flips a single reversal bit r[i] ∈ {0, 1} rather than comparing two sibling children first). Consequently, constructing a weak heap on n elements requires exactly n − 1 comparisons, and the resulting sorting algorithm—WeakHeapsort—sorts n elements in place (plus n bits) using at most n ⌈log₂ n⌉ − 2^{⌈log₂ n⌉} + n − 1 ≤ n log₂ n + 0.0861n worst-case comparisons, coming within 0.0861n comparisons of the information-theoretic lower bound ⌈log₂(n!)⌉ ≈ n log₂ n − 1.4427n.

The Three Defining Axioms of a Weak Heap

In a classical binary max-heap, every node must be greater than or equal to both its left child and its right child, which forces sift-down to perform 2 comparisons per level (one between the two children, and one between the larger child and the sifted element). A max-weak heap (the orientation used in WeakHeapsort; a min-weak heap reverses the inequality) relaxes this requirement into three axioms over a binary tree of n nodes:

1. Right-subtree dominance (half-ordering): The key of every node x is greater than or equal to the keys of all nodes in the right subtree of x (meanwhile, keys in the left subtree of x bear no ordering relation to x).
2. Root has no left child: The root node at index 0 has only a right child (at index 1) and an empty left subtree; therefore, by Axiom 1, the root dominates every other node in the entire tree and holds the global maximum at A[0].
3. Near-complete leaf depth: Leaves (nodes with fewer than two children) reside only on the last two levels of the tree.

Looked at through the left-child, right-sibling correspondence between binary trees and ordered forests, the right child of A[0] (at A[1]) together with the chain of left children descending from A[1] (indices 2, 4, 8, …) are the children of the root A[0] in a stretched binomial tree B_k, and each node x along that chain is the root of a sub-binomial tree consisting of x and the right subtree of x.

Implicit Array Indexing with the Reversal Bit Vector r

To swap the left and right subtrees of any node i in O(1) time without moving subtree elements in memory, a weak heap maintains an array of keys A[0 .. n − 1] alongside an array of single-bit flags r[0 .. n − 1] ∈ {0, 1}ⁿ (requiring just n bits, or ⌈n / 64⌉ machine words). For any node index i ≥ 1:

• Left child of i:

• Right child of i:

• Parent of i (in the underlying binary tree):

Observe that when r[i] = 0, the left child is 2i and the right child is 2i + 1; flipping the single bit r[i] ← 1 − r[i] exchanges the roles of left(i) and right(i) across the entire subtrees rooted at 2i and 2i + 1 in O(1) time with zero element movements.

Distinguished Ancestor Navigation and the Pairwise Join Primitive

In a half-ordered binary tree, a node x is directly constrained in heap order not by its immediate binary-tree parent ⌊x / 2⌋ (if x is a left child), but by its distinguished ancestor (also called its grandparent in Dutton's terminology)—the lowest ancestor of x that contains x inside its right subtree. Given any index j ≥ 1, its distinguished ancestor DistinguishedAncestor(j) is found by walking up the parent chain while j is a left child, and then taking one final step to the parent of which it was a right child:

1. While (j mod 2) = r[⌊j / 2⌋] (meaning j is currently the left child of ⌊j / 2⌋), set j ← ⌊j / 2⌋.
2. Return ⌊j / 2⌋.

In the binomial-tree isomorphism, two weak sub-heaps rooted at i (where i = DistinguishedAncestor(j)) and j (where j lies on the left spine of i's right child, so j's own left subtree is empty for the comparison) are combined by the join(i, j) primitive in 1 comparison:

• Compare A[i] and A[j].
• If A[j] > A[i] (in a max-weak heap), swap A[i] ↔ A[j] and flip the reversal bit r[j] ← 1 − r[j] (so that the former right subtree of j, which was dominated by the old A[j], remains the right subtree of the new A[j] = old A[i] after the swap).

Bottom-Up Construction in Exactly n − 1 Comparisons

To construct a weak heap from an arbitrary unsorted array A[0 .. n − 1]:

1. Initialize all reversal bits r[0 .. n − 1] ← 0.
2. For j = n − 1 down to 1, compute i ← DistinguishedAncestor(j) and execute join(i, j).

Because the loop executes join(i, j) once for each index j ∈ {1, 2, …, n − 1} and each join performs 1 key comparison, weak-heap construction always performs precise n − 1 comparisons in the worst, average, and best cases—matching the theoretical minimum number of comparisons required to identify the maximum of n elements. Moreover, although DistinguishedAncestor(j) loops over left-child steps, each edge in the binary tree is traversed at most once across the entire bottom-up sweep, so total construction time is bounded by O(n).

WeakHeapsort Worst-Case and Average-Case Comparison Bounds

Once the weak heap is constructed in n − 1 comparisons, WeakHeapsort extracts keys in sorted order from m = n − 1 down to 1:

1. Swap the maximum at A[0] with A[m] (placing the largest remaining key into its final sorted slot A[m]).
2. Walk down the left spine of A[1] inside the remaining range [1 .. m − 1]: starting at x ← 1, while left(x) < m, set x ← left(x), pushing the visited spine indices onto a small stack (or walking back up via parent(x) = ⌊x / 2⌋).
3. For each spine node x from bottom to top, execute join(0, x) to restore the new maximum at A[0].

During step m, the length of the left spine descending from A[1] is at most ⌈log₂ m⌉, so restoring the weak heap performs at most ⌈log₂ m⌉ comparisons (1 per level). Summing over m = 2, …, n − 1 together with the initial n − 1 construction comparisons yields Dutton's precise worst-case bound:

As analyzed by Edelkamp and Wegener (2000), the average number of comparisons of WeakHeapsort on random permutations lies between n log₂ n − 0.42n and n log₂ n − 0.46n, with variance O(n).

Beyond static sorting, Edelkamp, Elmasry, and Katajainen (2012, 2013) proved that the weak heap supports the full priority queue repertoire with optimal constant factors:

• insert in O(1) amortized (and worst-case) comparisons: Placing a new element at leaf index n (and initializing r[n] ← 0; if n is even, setting r[n / 2] ← 0 so n starts as a left child) and sifting upward via DistinguishedAncestor takes at most ⌈log₂ n⌉ comparisons in the worst case and O(1) amortized time; buffering at most 2 elements per level yields a worst-case O(1) insert priority queue.
• decrease-key in ⌈log₂ n⌉ comparisons: Decreasing (in a min-weak heap) the key at index x repeatedly executes join(DistinguishedAncestor(x), x) and sets x ← DistinguishedAncestor(x) until the join does not swap, performing at most 1 comparison per ancestor level.
• Bitless weak heaps via index navigation: By replacing the explicit bit array r[0 .. n − 1] with a two-child index mapping or storing the reversal state implicitly in the relative key order of twin pairs, weak-heap navigation can also be implemented in bounded by O(1) extra words at the cost of a small additive linear comparison term.

How does a weak heap achieve 1 comparison per level during delete-max instead of 2?

In a standard binary heap, deleting the root leaves a hole at the top; to fill that hole from its two children, the algorithm must compare the left child against the right child (1 comparison) and then compare the winner against the replacement element (a 2nd comparison). In a weak heap, the root A[0] has only a single child A[1], and deleting A[0] exposes the left spine of A[1]—a sequence of at most ⌈log₂ n⌉ sub-binomial trees of orders 0, 1, …, k − 1. Merging those sub-trees back from smallest to largest via join is identical to linking binomial trees in a binomial heap: each step compares only the two roots of the trees being linked (1 comparison per level) and flips a single bit in r to swap subtrees in constant time.

How much memory does the reversal bit array r require in practice?

Because each entry r[i] is a single Boolean bit (0 or 1), packing 64 bits into each 64-bit unsigned integer word (uint64) requires only ⌈n / 64⌉ words—or 1.56% of the space of an array of 64-bit keys (for example, sorting 1,000,000 64-bit integers uses 8 megabytes for the array A and just 125 kilobytes for the bit vector r, which fits completely inside the CPU's L1/L2 cache).

Why is WeakHeapsort's worst-case comparison bound n log2 n + 0.086n when log2 n is not an integer?

The precise worst-case formula C_worst(n) = n ⌈log₂ n⌉ − 2^{⌈log₂ n⌉} + n − 1 equals n log₂ n − 1 whenever n = 2^k is an precise power of two. The fractional excess over n log₂ n reaches its maximum when n / 2^{⌈log₂ n⌉} = 1 / ln 2 ≈ 0.7213, where the coefficient is 1 + log₂(ln 2) − (1 / ln 2) ≈ +0.0860713, giving the universal upper bound n log₂ n + 0.0861n for all n.

1. Dutton, R. D. (1993). "Weak-heap sort." BIT Numerical Mathematics, 33(3), 372–381. https://doi.org/10.1007/BF01990520
2. Edelkamp, S., & Wegener, I. (2000). "On the performance of WEAK-HEAPSORT." In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2000), Lecture Notes in Computer Science, Vol. 1770, 254–266. https://doi.org/10.1007/3-540-46541-3
3. Edelkamp, S., Elmasry, A., & Katajainen, J. (2012). "The weak-heap data structure: Variants and applications." Journal of Discrete Algorithms, 16, 187–205. https://doi.org/10.1016/j.jda.2012.04.010
4. Edelkamp, S., Elmasry, A., & Katajainen, J. (2013). "Weak heaps Engineered." ACM Journal of Experimental Algorithmics, 18, Article 1.1. https://doi.org/10.1145/2444016.2444017