Radix Heap

Radix heap is a specialized monotone priority queue data structure within computation and algorithms that maintains a dynamic set of items with non-negative integer keys drawn from a bounded span [0, C], supporting Insert and Decrease-Key in O(1) time and Extract-Min in O(log C) time via amortized analysis. Introduced by Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, and Robert E. Tarjan in the Journal of the ACM in 1990, the radix heap exploits the monotonicity property of Dijkstra's algorithm on directed graphs with non-negative integer edge weights w(u, v) ∈ {0, 1, ..., C}: namely, the sequence of minimum keys extracted over time is monotonically non-decreasing, and no newly inserted or decreased key is ever smaller than the most recently extracted minimum key d_min.

By replacing a general comparison-based priority queue such as a Fibonacci heap, hollow heap, or d-ary heap with an array of B = ⌈log₂(C + 1)⌉ + 2 buckets whose key intervals double in width with bucket index (1, 1, 2, 4, 8, ..., 2^B−3), a one-level radix heap reduces the running time of Dijkstra's shortest-path algorithm on an n-vertex, m-edge graph from O(m + n log n) to O(m + n log C), while a two-level radix heap combined with a Fibonacci heap achieves O(m + n √(log C)).

In single-source shortest-path computation via Dijkstra's algorithm on a graph G = (V, E) with integer edge lengths 0 ≤ w(u, v) ≤ C, let d(v) denote the tentative distance label of vertex v, and let d_min denote the distance label of the vertex most recently extracted from the priority queue. Because every edge weight satisfies w(u, v) ≥ 0, relaxing an outgoing edge (u, v) from the extracted vertex u (where d(u) = d_min) assigns a candidate distance d(u) + w(u, v) that always lies in the sliding interval:

• d_min ≤ d(u) + w(u, v) ≤ d_min + C.

In 1969, Robert B. Dial observed that because all active finite distance labels in the priority queue simultaneously reside within an interval of width at most C + 1, one can maintain an array of C + 1 circularly indexed buckets, each of width 1. While Dial's algorithm performs Insert and Decrease-Key in O(1) time, scanning empty buckets during n Extract-Min operations requires O(m + nC) time and O(C) space, which becomes pseudo-polynomial when the maximum edge weight C is large (for example, C = 2³²). A radix heap compresses those C + 1 unit buckets into B = O(log C) variable-width buckets whose sizes grow as powers of two away from d_min.

A one-level binary radix heap maintains B = ⌈log₂(C + 1)⌉ + 2 doubly linked lists (buckets) indexed k = 0, 1, ..., B − 1, accompanied by an array of integer interval bounds u[0], u[1], ..., u[B], where bucket k stores all active items whose current integer keys fall in the closed integer interval [u[k], u[k + 1] − 1].

Exponentially Doubling Bucket Widths

The bucket capacities (widths) size(k) = u[k + 1] − u[k] follow the exponential base-2 progression w_k = 2^k−1 = e^{(k−1) ln 2} for k ≥ 1:

• Bucket 0 (k = 0): Width size(0) = 1, covering the single integer [u[0], u[0]] where u[0] = d_min.
• Bucket 1 (k = 1): Width size(1) = 1, covering [u[1], u[1]].
• Bucket 2 (k = 2): Width size(2) = 2, covering an interval of 2 integers.
• Bucket k (1 ≤ k ≤ B − 2): Width size(k) = 2^k−1 integers.
• Sentinel Bucket B − 1: Upper bound u[B] = +∞, holding vertices whose tentative distance labels are still infinite or reach the upper horizon.

Initially, before any extraction occurs (d_min = 0), the interval lower bounds are initialized as u[0] = 0 and u[k] = 2^k−1 for 1 ≤ k ≤ B − 1. Because the sum of the widths of the first k buckets (0 through k − 1) is:

• 1 + ∑_j=1^k−1 2^j−1 = 1 + (2^k−1 − 1) = 2^k−1 = size(k),

the radix heap satisfies a foundational redistribution invariant: the total integer span of all buckets below bucket k (buckets 0, 1, ..., k − 1 combined) is always at least as large as the width 2^k−1 of bucket k itself.

Bitwise XOR Representation of Bucket Index

An equivalent implementation avoids maintaining explicit interval endpoints u[k] by tracking only the last extracted minimum key lastDeleted = d_min. For any item with key x ≥ lastDeleted, let diff = x ⊕ lastDeleted be the bitwise exclusive-OR of x and lastDeleted. The item belongs in bucket:

• k = 0 if x = lastDeleted (diff = 0), and
• k = ⌊log₂(x ⊕ lastDeleted)⌋ + 1 (the 1-based bit position of the most significant bit where the binary representations of x and lastDeleted differ) if x > lastDeleted.

Because modern processors compute leading-zero counts in a single clock cycle, finding the target bucket for any key takes O(1) worst-case time in the word-RAM model.

Insert and Decrease-Key

• Insert(e, x): Given a new item e with key x ∈ [d_min, d_min + C], determine its bucket index k and insert e into the doubly linked list of bucket k.
• Decrease-Key(e, x_new): When an item e currently residing in bucket k has its key decreased from x_old to x_new (with d_min ≤ x_new < x_old), check whether x_new ≥ u[k]. If x_new still lies inside bucket k's interval, no structural movement is required. Otherwise, remove e from bucket k and walk downward through k − 1, k − 2, ... until finding the bucket j < k containing x_new (or jump directly in O(1) time using bitwise XOR).

Because x_new < x_old and the lower bounds u[k] only increase during Extract-Min, an item's bucket index k can only decrease over its entire lifetime in the radix heap.

Extract-Min and Bucket Redistribution

To execute Extract-Min:

1. Fast Path (k = 0 Non-Empty): If bucket 0 is non-empty, all items in bucket 0 share the key u[0] = d_min (since size(0) = 1). Remove and return any item from bucket 0 in O(1) worst-case time.
2. Bucket Redistribution (k > 0): If bucket 0 is empty, scan k = 1, 2, ..., B − 1 to find the smallest index k such that bucket k is non-empty.
   • Scan all items currently in bucket k to find the minimum key x_min among them, and set d_min ← x_min.
   • Re-anchor the lower bounds of buckets 0 through k − 1 starting at u[0] = x_min: set u[1] = x_min + 1, and for j = 2, ..., k − 1, set u[j] = min(u[j − 1] + 2^j−2, u[k + 1]). Finally set u[k] = u[k + 1].
   • Remove every item e from bucket k and insert it into its newly assigned narrower bucket j ∈ {0, 1, ..., k − 1}. Because the combined capacity of buckets 0 through k − 1 is 2^k−1, which equals or exceeds the span [x_min, u[k + 1] − 1] of the items in bucket k, every redistributed item moves to a lower-indexed bucket j < k.
   • Bucket 0 is now guaranteed to contain the item(s) with key x_min; remove and return one such item.

Amortized Time Complexity Proof

Define the potential function of the radix heap as the sum of the current bucket indices of all active items e in the heap:

• Φ = ∑_{e ∈ H} bucket(e).

When an item e is first inserted into the heap, bucket(e) ≤ B − 1 = O(log C). Every time an item is moved during a Decrease-Key scan or redistributed out of bucket k during Extract-Min, its bucket index bucket(e) decreases by at least 1 (j ≤ k − 1), releasing at least 1 unit of potential to pay for its O(1) list transfer. Since bucket(e) starts at ≤ ⌈log₂(C + 1)⌉ + 1 and can never drop below 0, no item can be redistributed or shifted across buckets more than O(log C) times in total across the execution of the algorithm. Scanning the B = O(log C) bucket headers during each of the n Extract-Min operations costs O(n log C) total time, and m Decrease-Key operations cost O(m) time, yielding a total runtime of O(m + n log C) for Dijkstra's algorithm.

To reduce the O(log C) factor further, Ahuja et al. generalized the binary radix heap from base 2 to an arbitrary integer radix K ≥ 2 (a two-level or multi-level radix heap):

• Instead of 1 bucket of each power-of-two width, each level i consists of K − 1 sub-buckets of width Kⁱ⁻¹, reducing the number of levels from log₂ C to L = ⌈log_K(C + 1)⌉ = O((log C) / (log K)).
• Choosing K = ⌈(log C)^1/2⌉ in a two-level segment architecture reduces the runtime to O(m + (n log C) / log log C).
• Furthermore, by maintaining the non-empty bucket headers inside a Fibonacci heap and balancing the number of radix levels against the Fibonacci heap extraction cost, Ahuja, Mehlhorn, Orlin, and Tarjan achieved the classic hybrid bound of O(m + n √(log C)) for single-source shortest paths with non-negative integer arc lengths.

Why can a radix heap not be used as a general-purpose priority queue?

A radix heap relies on the monotonicity invariant: no key inserted into the heap (or produced by Decrease-Key) may ever be smaller than the key d_min of the most recently extracted minimum item. In a general priority queue where an arbitrary small key x < d_min can arrive at any time, bucket 0's lower bound u[0] = d_min has already advanced past x, so no bucket exists to hold x. Because Dijkstra's algorithm with non-negative edge weights never produces a distance label smaller than the current minimum d_min, it satisfies monotonicity automatically.

Why can a radix heap not directly accelerate Prim's minimum spanning tree algorithm?

Unlike Dijkstra's algorithm, which adds the non-negative edge weight w(u, v) to the monotonically increasing distance d(u) = d_min, Prim's algorithm updates vertex keys to w(u, v) itself (which may be much smaller than the weight of the edge most recently added to the spanning tree). Because extracted edge weights in Prim's algorithm are not monotonically non-decreasing, a standard monotone radix heap cannot be used directly for Prim's algorithm (where a Fibonacci heap, hollow heap, or soft heap-based algorithm is used instead).

When is a radix heap faster than a Fibonacci heap for Dijkstra's algorithm?

In theoretical asymptotic terms, O(m + n log C) beats O(m + n log n) whenever log C = o(log n) (that is, when edge weights are small or moderate integers). Even when C ≤ 2³² or 2⁶⁴ on fixed-word-size hardware, a binary radix heap requires at most 33 or 65 contiguous array buckets and simple doubly linked list splices (plus a single hardware leading-zero count instruction), avoiding the pointer chasing, heap allocations, and high constant factors of Fibonacci heaps in practical road-network routing.

1. Ahuja, R. K., Mehlhorn, K., Orlin, J. B., & Tarjan, R. E. (1990). "Faster Algorithms for the Shortest Path Problem." Journal of the ACM, 37(2), 213–223. https://doi.org/10.1145/77600.77615
2. Dial, R. B. (1969). "Algorithm 360: Shortest-Path Forest with Topological Ordering [H]." Communications of the ACM, 12(11), 632–633. https://doi.org/10.1145/363269.363610
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. Cherkassky, B. V., Goldberg, A. V., & Silverstein, C. (1999). "Buckets, Heaps, Lists, and Monotone Priority Queues." SIAM Journal on Computing, 28(4), 1326–1346. https://doi.org/10.1137/S0097539796313490