Rank-Pairing Heap

Rank-Pairing Heap (often abbreviated as rp-heap) is a mergeable priority queue data structure in computation and algorithms that combines the asymptotic time optimality of a Fibonacci heap with the structural simplicity and practical speed of a pairing heap. Introduced by Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan at the 2009 European Symposium on Algorithms (ESA) and published in the SIAM Journal on Computing in 2011, the rank-pairing heap supports Find-Min, Insert, Meld, and Decrease-Key in O(1) amortized time, and Delete-Min and Delete in O(log n) amortized time on an n-element collection. Unlike Fibonacci heaps, which maintain circular doubly linked child lists, parent pointers, and Boolean mark bits to drive recursive cascading cuts during Decrease-Key, a rank-pairing heap represents its forest as a circular singly linked list of half-ordered binary trees in which every Decrease-Key operation performs at most one tree cut, followed by a lightweight upward pass of local integer rank decrements.

Because node rebalancing after a key reduction is confined to integer arithmetic on single-byte node ranks rather than multi-node pointer detachments along the ancestor spine, rank-pairing heaps achieve low constant factors and high cache efficiency in network optimization routines such as Dijkstra's algorithm for single-source shortest paths and Prim's algorithm for minimum spanning trees.

Following Michael L. Fredman and Robert E. Tarjan's invention of the Fibonacci heap in 1984, algorithm designers sought a pointer-based priority queue that retained O(1) amortized Decrease-Key and O(log n) amortized Delete-Min without the four pointers per node (parent, leftmost child, left sibling, right sibling) and cascading-cut machinery required by Fibonacci trees. In 1986, Fredman, Robert Sedgewick, Daniel D. Sleator, and Tarjan proposed the pairing heap as a self-adjusting, rankless alternative inspired by the splay tree. Although pairing heaps proved fast in empirical benchmarks, Fredman established an information-theoretic lower bound showing that standard pairing heaps and cousin structures storing no subtree-size or rank metadata cannot achieve O(1) amortized Decrease-Key when Meld is O(1); Seth Pettie subsequently proved an Ω(log log n) amortized lower bound on Decrease-Key for pairing heaps.

To bridge this divide, several relaxed-rank priority queues were proposed between 1988 and 2009, including relaxed heaps, thick heaps, 2-3 heaps, violation heaps, and quake heaps. Haeupler, Sen, and Tarjan designed the rank-pairing heap by asking what minimal rank invariant suffices to preserve an exponential subtree-size lower bound s(x) ≥ φ^r = exp(r ln φ) when every Decrease-Key detaches at most a single subtree and never performs a second cut. Their resulting structure stores only one non-negative integer rank per node and represents heap-ordered multiway trees via the standard binary-tree correspondence, requiring just three pointers per node.

A rank-pairing heap consists of a collection of half-ordered binary trees (also called half trees) whose roots are connected in a circular singly linked list accessed through a pointer to the minimum-key root minRoot. In the classical correspondence between an ordered multiway heap tree and a binary tree—used in pairing heaps and binomial queues—the left child pointer left(x) of a node x points to the first (most recently linked) child of x in the multiway tree, while the right child pointer right(x) points to the next sibling of x in the multiway parent's child list.

The Half-Order Invariant

In a half-ordered binary tree, keys obey a directional ordering condition rather than the symmetric two-child constraint of a standard binary heap or treap:

• For every node x in a half tree, key(x) is less than or equal to the key of every node located in the left subtree of x: for all y in the subtree rooted at left(x), key(x) ≤ key(y).
• No ordering constraint is imposed between key(x) and the keys of nodes in the right subtree of x, because nodes reachable along the right spine of left(x) are all children of x in the underlying multiway tree and therefore all have keys at least key(x), though they are unordered relative to one another.
• Every root u of a half tree in the root list has an empty right subtree (right(u) = null) and a potentially non-empty left subtree rooted at left(u) containing all descendants of u.

Consequently, the minimum key in any half tree always resides at its root u, and the global minimum across the priority queue is found at minRoot in O(1) worst-case time.

Node Pointer Layout and Memory Footprint

Each internal node x inside a half tree stores three structural pointers and one small integer rank field:

1. left(x): Points to the left child of x in the half-tree representation (the head of x's child spine).
2. right(x): Points to the right child of x (the next sibling along the parent's right spine; for a root u, right(u) serves as the circular next-root pointer in the top-level root list).
3. parent(x): Points to the binary-tree parent p(x) of x in the half tree (for a root u, parent(u) = null).
4. rank(x): A non-negative integer r(x) ≥ 0 stored in a single byte, bounded above by ⌊log_φ n⌋ + 1 for Type-2 rp-heaps.

Unlike a Fibonacci heap node, which stores four machine-word pointers plus a rank and a mark bit, a rank-pairing heap node eliminates one pointer and the mark bit, matching the three-pointer footprint of a hollow heap, red-black tree, or AVL tree.

To guarantee that a half tree whose root has rank r contains at least an exponential number of nodes F_r+2 ≥ φ^r = exp(r ln φ), every node x maintains a non-negative integer rank r(x). By convention, a missing (null) child is assigned a virtual rank of −1: r(null) = −1. Every leaf in the binary representation (left(x) = null and right(x) = null) has rank 0.

For any non-root node x with binary parent p(x), the rank difference of x is defined as:

Δr(x) = r(p(x)) − r(x)

Every root u of a half tree has right(u) = null and satisfies Δr(left(u)) = r(u) − r(left(u)) = 1; thus, the rank of any root u is always r(left(u)) + 1. For any non-root node x, its two binary children left(x) and right(x) have rank differences {Δr(left(x)), Δr(right(x))}. A node x with unordered child rank differences {i, j} is termed an (i, j)-node.

Ranked Fair Links and Pure Half Trees

When two half-tree roots u and v of equal rank k (r(u) = r(v) = k) are combined by a fair link (assuming key(u) ≤ key(v)), v is attached as the new left child of u, and the old left child of u becomes the right child of v:

• Set right(v) = left(u) and parent(left(u)) = v (if left(u) ≠ null).
• Set left(u) = v and parent(v) = u.
• Increment r(u) from k to k + 1 while keeping r(v) = k.

If a rank-pairing heap is built using only Insert, Meld, and Delete-Min (with no Decrease-Key cuts), every non-root node x is a (1, 1)-node: both left(x) and right(x) have rank r(x) − 1, so the half tree is isomorphic to a binomial tree of size 2^k.

Type-1 and Type-2 Rank Rules Under Decrease-Key

When Decrease-Key detaches subtrees from the interior of a half tree, the (1, 1) binomial balance is relaxed. Haeupler, Sen, and Tarjan defined two variants of the rank rules governing non-root nodes:

1. Type-1 Rank-Pairing Heap: Every root u has Δr(left(u)) = 1 and right(u) = null. Every non-root node x must be either a (1, 1)-node or a (0, i)-node with i ≥ 2 (meaning one child has rank difference 0 and the other child has rank difference at least 2).
2. Type-2 Rank-Pairing Heap: Relaxes the Type-1 rule so that every non-root node x is a (1, 1)-node, a (1, 2)-node, or a (0, i)-node with i ≥ 2.

Subtree Size Lower Bounds

The choice between Type-1 and Type-2 rules determines the base of the geometric lower bound on the number of descendants s(x) in the binary subtree rooted at x:

• Type-2 Subtree Bound (Golden Ratio Base): In a Type-2 rp-heap, a node x of rank k has at least F_k+2 − 1 descendants in its binary subtree, so a half tree whose root has rank k contains at least F_k+2 ≥ φ^k = e^{k ln φ} nodes, where φ = (1 + √5) / 2 ≈ 1.61803. Thus, the maximum rank in a Type-2 rp-heap of n elements is at most ⌊log_φ n⌋ ≈ 1.4404 log₂ n.
• Type-1 Subtree Bound: In a Type-1 rp-heap, because (1, 2)-nodes are forbidden, the minimum number of nodes in a half tree of root rank k satisfies S_k = S_k−1 + S_k−3 ≥ c · α^k = c · e^{k ln α} where α ≈ 1.46557 is the real root of α³ − α² − 1 = 0, giving a maximum rank ≤ 1.8133 log₂ n alongside a tighter amortized constant factor during Delete-Min consolidation.

Find-Min, Insert, and Meld in O(1) Time

All three non-deleting operations act on the circular singly linked root list in O(1) worst-case time:

• Find-Min(H): Returns the item stored at minRoot(H) in O(1) worst-case time.
• Insert(x, k, H): Initializes a singleton half tree rooted at x with left(x) = right(x) = parent(x) = null and r(x) = 0, splices x into the circular root list of H, and updates minRoot(H) if k < key(minRoot(H)).
• Meld(H₁, H₂): Concatenates the circular singly linked root lists of H₁ and H₂ in O(1) worst-case time and sets minRoot to whichever of minRoot(H₁) and minRoot(H₂) holds the smaller key.

Decrease-Key via One Cut and Rank-Difference Restoration

Suppose Decrease-Key(x, k, H) lowers the key of node x to k < key(x). If x is already a root (parent(x) = null), the algorithm updates key(x) = k and compares k against key(minRoot(H)) in O(1) time.

If x is a non-root node with binary parent u = parent(x), nodes in the right subtree of x (y = right(x)) are multiway siblings of x rather than descendants of x; their keys do not depend on key(x). Therefore, the algorithm detaches x along with its left subtree left(x), while leaving y = right(x) attached in x's former slot inside the half tree:

1. Single Subtree Detachment: Replace x with y = right(x) as the appropriate child (left or right) of u = parent(x), and set parent(y) = u (if y ≠ null). Set right(x) = null and parent(x) = null, set r(x) = r(left(x)) + 1, and insert the new half-tree root x into the circular root list.
2. Upward Rank-Decrement Ripple (No Cascading Cuts): Starting at u, walk up the ancestor chain u ← parent(u), adjusting r(u) downward when needed to restore the Type-1 or Type-2 rank rules:
   • In a Type-2 rp-heap, while u is not a root, let v and w be the two children of u with r(v) ≤ r(w). Define target rank k = r(w) if r(w) − r(v) > 1, or k = r(w) + 1 if r(w) − r(v) ≤ 1. If k ≥ r(u), the Type-2 invariant holds at u and the upward walk terminates at once; otherwise, set r(u) = k and advance u ← parent(u). If the walk reaches the half-tree root u, set r(u) = r(left(u)) + 1.
   • In a Type-1 rp-heap, the same upward walk sets k = r(w) + 1 whenever r(v) = r(w), and k = r(w) whenever r(v) < r(w).

This upward pass never cuts another edge and modifies only the 1-byte integer r(u) field along the ancestor path until a node's rank stabilizes.

Delete-Min via Bucket Consolidation

During Delete-Min(H), the minimum root m = minRoot(H) is removed from the root list, and its left subtree left(m) is dismantled along its right spine into individual half-tree roots. Using an array B[0 .. R] of root buckets indexed by rank (R ≤ ⌊log_φ n⌋), roots of equal rank are combined by fair links (either in a one-pass mode that moves each linked pair directly to the output root list, or in a multipass mode that continues linking at rank r + 1), completing Delete-Min in O(log n) amortized time.

To prove that Decrease-Key takes O(1) amortized time despite the upward rank-decrement loop, Haeupler, Sen, and Tarjan assigned a potential ϕ(x) to every node x based on its child rank differences:

• In a Type-2 rank-pairing heap, every (1, 1)-node and (1, 2)-node carries potential 1, whereas every (0, i)-node carries potential 0.
• Whenever the upward loop during Decrease-Key decrements r(u) by 1, u transitions into a (0, i)-node with potential 0 (because the unchanged child w now has rank equal to the decremented r(u), so Δr(w) = 0).
• Thus, each step of the upward rank-decrement loop releases 1 unit of stored potential from u, paying for the O(1) work of visiting u. Only the final node where the loop stops may gain 1 unit of potential, yielding O(1) amortized time per Decrease-Key, Insert, and Meld, and O(log n) amortized time per Delete-Min.

How does a rank-pairing heap differ from a standard pairing heap?

A standard pairing heap stores no rank information at its nodes; during Delete-Min, it pairs dismantled children from left to right regardless of subtree size, which prevents it from achieving O(1) amortized Decrease-Key. A rank-pairing heap adds a 1-byte integer rank field r(x) to each node in the half-ordered binary tree, links roots of equal rank via buckets during Delete-Min, and updates ancestor ranks after the single cut in Decrease-Key, securing the optimal O(1) amortized Decrease-Key bound of a Fibonacci heap.

Why does Decrease-Key in a rank-pairing heap never perform cascading cuts?

In a Fibonacci heap, losing a second child forces a node to be cut from its parent. In a rank-pairing heap, the binary half-tree representation allows a node u to absorb the loss of a subtree by turning into a (0, i)-node—decrementing r(u) so that one binary child has rank difference 0 while the other has an arbitrarily large rank difference i ≥ 2. Because (0, i)-nodes carry zero potential, propagating rank decrements upward releases stored potential without ever severing a second tree edge.

When should Type-1 vs. Type-2 rank-pairing heaps be used?

Type-2 rank-pairing heaps permit (1, 2)-nodes in addition to (1, 1)- and (0, i)-nodes, which terminates the upward rank-decrement ripple earlier during Decrease-Key and guarantees a smaller maximum rank (⌊log_φ n⌋ ≈ 1.44 log₂ n vs. 1.81 log₂ n for Type-1). Type-2 rp-heaps are therefore preferred in implementations of Dijkstra's algorithm where Decrease-Key calls outnumber Delete-Min calls.

1. Haeupler, B., Sen, S., & Tarjan, R. E. (2011). "Rank-Pairing Heaps." SIAM Journal on Computing, 40(6), 1463–1485. https://doi.org/10.1137/100785351
2. Haeupler, B., Sen, S., & Tarjan, R. E. (2009). "Rank-Pairing Heaps." In Algorithms – ESA 2009, Lecture Notes in Computer Science, vol. 5757, pp. 659–670. Springer. https://doi.org/10.1007/978-3-642-04128-0
3. Fredman, M. L., & Tarjan, R. E. (1987). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM, 34(3), 596–615. https://doi.org/10.1145/28869.28874
4. Fredman, M. L., Sedgewick, R., Sleator, D. D., & Tarjan, R. E. (1986). "The Pairing Heap: A New Form of Self-Adjusting Heap." Algorithmica, 1(1–4), 111–129. https://doi.org/10.1007/BF01840439
5. Pettie, S. (2005). "Towards a Final Analysis of Pairing Heaps." In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 174–183. https://doi.org/10.1109/SFCS.2005.75
6. Hansen, T. D., Kaplan, H., Tarjan, R. E., & Zwick, U. (2017). "Hollow Heaps." ACM Transactions on Algorithms, 13(3), Article 42, 1–27. https://doi.org/10.1145/3093240