Radix heaps: queue nondecreasing integer priorities

Last updated: 5 Oct 20269 min read

tutorial

A radix heap is useful when priorities are nonnegative integers and no later insertion can fall below the last priority removed. It groups entries by the bit length of priority XOR the last removed priority. Bucket zero contains keys equal to that last value. If bucket zero is empty, the queue finds the first nonempty bucket, makes its smallest priority the new last value, and redistributes that bucket under the new difference. The monotone rule makes that redistribution safe: a future key cannot undercut an already extracted priority. This program rejects a lower inserted priority and returns the stored incident with its priority. It gives no stable order among equal priorities and cannot act as a general-purpose queue for arbitrary decreases.

Operational case

A shortest-route worker extracts distances 19, 19, 47, and 61 from four initially pending incidents. A new candidate at priority 18 after the worker has removed priority 19 would violate the queue contract and raises instead of silently misplacing the entry. Nonnegative edge-weight route searches can satisfy the monotone extraction rule when they insert tentative distances after processing the current minimum. Negative edges and workloads that reprioritize old work downward do not satisfy it. The example prints priorities only because equal-priority incident order is unspecified.

Working Python program


class MonotoneIncidentQueue:
    def __init__(self):
        self.last = 0
        self.buckets = [[]]
        self.size = 0

    def push(self, priority, incident_id):
        if not isinstance(priority, int) or priority < self.last:
            raise ValueError("priority must be an integer at least the last extracted priority")
        level = (priority ^ self.last).bit_length()
        while len(self.buckets) <= level:
            self.buckets.append([])
        self.buckets[level].append((priority, incident_id))
        self.size += 1

    def pop(self):
        if not self.size:
            raise IndexError("empty priority queue")
        if not self.buckets[0]:
            level = next(index for index, bucket in enumerate(self.buckets) if bucket)
            pending = self.buckets[level]
            self.buckets[level] = []
            self.last = min(priority for priority, _ in pending)
            for entry in pending:
                new_level = (entry[0] ^ self.last).bit_length()
                self.buckets[new_level].append(entry)
        self.size -= 1
        return self.buckets[0].pop()


queue = MonotoneIncidentQueue()
for priority, incident_id in ((47, "pump-47"), (19, "valve-19"),
                              (61, "sensor-61"), (19, "grid-83")):
    queue.push(priority, incident_id)
print("priorities=", [queue.pop()[0] for _ in range(4)], sep="")

Output

priorities=[19, 19, 47, 61]

Time, space, and tradeoff

Let W be the maximum bit width reached by a key difference and N the number of accepted entries. Push computes one bucket index and appends in O(1) bucket work plus integer bit operations. A pop can scan O(W) buckets and redistribute O(N) entries in one call, so it has no logarithmic worst-case latency claim. Each entry changes buckets at most O(W) times as the last value grows, giving O(NW) total redistribution work over a finite-width batch; storage is O(N+W). Python integers are unbounded, so W is workload-dependent. The code does not handle deletion, decrease-key, or stable ties.

Common Mistakes

Do not insert a priority below the last extracted value.
Do not sort equal priorities by incident ID unless the API promises that order.
Do not call one redistribution pop constant time.
Do not apply the queue to negative-weight route updates.

Connected lessons

Compare its queue operations with Pairing heaps: meld roots and pair children on removal, Binomial heaps: carry equal-degree trees during merge, Double-ended queues: reconcile min and max heaps, then run the priority-queue audit and contract quiz.

data structures

trees-and-heaps