Monotone Integer Keys: Bucket Queues and Radix Heaps

Every structure discussed so far compares keys. A comparison-based priority queue cannot beat Ω(log n) per extraction, because n elements have n! possible orderings and each comparison distinguishes at most two, so the decision tree must have depth at least log₂ n! ≈ n log n over a full drain. That bound is about the information the structure has, not about the problem. When keys are small integers and the sequence of extracted keys is known to be nondecreasing — the situation in Dijkstra’s algorithm with nonnegative weights, and in event simulation with a bounded lookahead — the keys carry more structure than a comparison exposes, and the bound does not apply.

Two structures exploit this. The bucket queue, introduced by Dial in 1969 for shortest paths, keeps an array indexed directly by key value. The radix heap keeps buckets indexed by the position of the most significant differing bit. The bucket queue pays nothing per element and everything per possible key difference; the radix heap shrinks the number of buckets to the width of the key in bits.

Direct addressing and the circular array

The simplest monotone queue is an array of C + 1 buckets, where C is the largest key difference the algorithm can produce. Bucket k holds a list of elements whose key is exactly k. The queue maintains a cursor at the current minimum key; extraction pops from that bucket, and when it empties, the cursor advances to the next nonempty bucket.

Insertion appends to bucket key mod (C + 1) in O(1). Extraction pops from the cursor in O(1) amortised, with the total cost of advancing the cursor bounded by the range of keys examined over the whole run. The structure has no comparisons at all — not even one — and no logarithmic factor.

The modular indexing is what makes the array reusable across a long run. Keys are not bounded above; only the spread of the live window matters. If the algorithm guarantees that every key it inserts lies in the interval from the cursor to cursor + C, then all live keys occupy at most C + 1 consecutive values, and key mod (C + 1) is injective over that set: two distinct values in the interval cannot differ by a multiple of C + 1. The array is a window that slides over the key axis as the cursor advances.

/* Bucket queue over keys in [0, C]; circular, so live keys fit any absolute range. */
typedef struct { int *head; } bucket_queue;   /* head[k] = first element with key k, or -1 */
static int next_nonempty(int *head, int C, int cur) {
    for (int step = 1; step <= C + 1; step++) {
        int k = (cur + step) % (C + 1);
        if (head[k] != -1) return k;
    }
    return -1;                                 /* queue empty */
}

The correctness of the sliding window depends on a precondition the structure cannot check: that no key smaller than the cursor is ever inserted. Violating it puts an element into a bucket that has already been passed, and it will never be extracted — or, worse, will be extracted one full cycle later, after the cursor wraps, silently producing results in the wrong order. Monotonicity is an assumption about the caller, and every use of a bucket queue rests on it.

The parameter C is the structure’s practical constraint. Dial’s original formulation uses C equal to the maximum edge weight in the graph, since any relaxation increases a distance by at most that amount, so the window need only span one edge’s worth of key; the array therefore has as many buckets as the largest single edge weight, not as many as the largest distance.

Radix heaps: buckets indexed by bits

A radix heap removes the dependency on C being small by organising buckets according to the binary representation of the key. For keys of B bits it keeps B + 1 buckets. One holds the elements whose key equals the current minimum. The other B are indexed by bit position, and bucket k holds the elements whose most significant bit of difference from the current minimum m is bit k, counting from the least significant bit. A key that differs from m in bit 0 only lands in bucket 0; a key that differs first at bit 5 lands in bucket 5, whatever its lower bits are.

Every key in bucket k is therefore greater than m, and differs from m first at bit k. That gives the property the structure exploits: the next minimum after m is the smallest element of the lowest nonempty bucket, because a key in a higher bucket differs from m at a more significant bit and so exceeds every key in a lower bucket.

Extracting that minimum requires redistributing the bucket it came from. The smallest element of the lowest nonempty bucket k becomes the new minimum m’, and every other element of bucket k is moved to the bucket matching its most significant difference from m’. Each of those keys agrees with m’ on every bit at or above position k, so its difference from m’ is set below position k: every element moves to a strictly lower bucket, and an element is redistributed at most B times. Each extraction can examine every element that has accumulated in the lowest nonempty bucket, so the cost is amortised rather than worst-case per call.

The total cost over n insertions and n extractions is O(n · B) = O(n log C) for keys up to C, with comparisons used only to find the minimum within a redistributed bucket. Each single redistribution therefore performs up to a linear scan of one bucket, which is what makes the bound amortised. That is the same asymptotic order as a binary heap’s O(n log n) in the element count, but the logarithm is over the key width rather than the element count, so it is a constant for a fixed word size: at most 32 redistributions per element for 32-bit keys, regardless of how many elements are in the queue.

The comparison with comparison-based heaps

The two structures occupy different points on the same trade. Both require integer keys and monotonicity of extraction; both replace comparisons with array indexing.

Property	Binary heap	Bucket queue	Radix heap
Extraction	O(log n)	O(1) amortised	O(log C) amortised
Insertion	O(log n)	O(1)	O(1) amortised
Memory	n keys + array	n keys + C slots	n keys + B bucket heads
Key type	any ordered	small integers	bounded integers
Monotone required	no	yes	yes

The radix heap’s extraction bound is amortised: a single call can scan a large bucket, and the total across a sequence is what stays within O(log C) per element.

The bucket queue’s weakness is the C + 1 slots, most of which are empty at any moment. With n = 10⁶ elements and C = 1000, the bucket array is three orders of magnitude smaller than the payload; with C = 10⁹, it holds a billion slots regardless of how few elements are pending, and the array alone exceeds the memory any binary heap would need. The radix heap’s B + 1 buckets do not scale with the key range, which makes it the better choice whenever the weights are large but bounded by the word size.

The radix heap’s weakness is the redistribution step, which is more complex than a sift-down and touches a whole bucket at once. The cost is amortised, but the worst case for a single extraction can be large: if a bucket holds many elements, the redistribution scans all of them. For latency-sensitive use, the bucket queue’s O(1) per operation is preferable.

Why Dijkstra’s algorithm is the natural home

Dijkstra’s algorithm relaxes edges and inserts tentative distances, and in each relaxation it inserts a distance derived from one it has just extracted, so nonnegative weights make the inserted values nondecreasing. That is exactly the monotonicity the structures require. With small integer weights and a maximum weight C, a circular bucket queue gives O(m + nC) for a graph with m edges and n vertices. The C in that bound is the maximum edge weight, which bounds the number of buckets a single extraction can scan, so the win is confined to small weights; when weights reach the size of the vertex count, the comparison-based heap is the better trade.

For floating-point or unbounded weights, monotonicity still holds but the integer indexing does not, and the radix heap does not apply either. The alternative there is a comparison-based heap with a position map, as indexed binary heaps describes. The choice between the two families is a question about the key domain, not about the graph.

There is a third option for the integer case that trades memory for simplicity: a multi-level bucket structure that partitions the key range into coarse and fine buckets, so the number of buckets is proportional to the square root of the range rather than the range itself. The structure is a generalisation of the circular bucket queue and appears in the shortest-path literature as a way to handle ranges too large for a flat array but too small for the complexity of a radix heap.

Failure modes specific to monotone structures

Monotonicity violations are the dominant failure. A decrease-key operation that lowers a key below the current minimum — which cannot happen in Dijkstra but can happen in other algorithms that use the same structures — inserts into a bucket the cursor has passed. Some implementations detect this by comparing the new key against the cursor and falling back to a comparison-based path; others document the requirement and leave the detection out.

Bucket overflow is the second. A bucket queue sized for C but given a key difference larger than C wraps modulo C + 1 and places the element in a bucket that is already occupied by a key differing by exactly C + 1. The two keys then share a bucket, and extraction order within the bucket depends on the list order, which is not key order. The error is silent and produces a plausible but incorrect result — the worst kind.

The third is the cursor advance loop. Advancing across every bucket once costs O(C) over the whole run, since the cursor never goes backward, which spreads to O(1) amortised per extraction. The bound holds only while the cursor is resumable: an implementation that scans the whole array from index zero on every extraction instead revisits every bucket once per call and degrades to O(nC) for a full drain.

None of these structures replaces the general-purpose heap. They are specialisations that win when the key domain is narrow and integer and the extraction order is monotone, and the narrowness of that condition is why standard libraries do not provide them. The general-purpose structures in this cluster — from the array-layout binary heap through the mergeable families — cover the cases where keys are arbitrary, and the specialised structures cover the rest.