Priority Queues for Dijkstra: Decrease-Key, Lazy Deletion, and Buckets

The greedy loop in Dijkstra and the Settled-Set Invariant needs exactly two queue operations: extract the minimum, and lower a key that is already in the queue. Everything else is bookkeeping. The design space is therefore narrow, and yet the constant factors differ by enough to change which implementation is the right one for a given graph, sometimes by a factor that matters more than the asymptotic class.

The two operations and their prices

Call $n = |V|$ and $m = |E|$. A run performs $n$ extractions and at most $m$ key lowerings. Write $T_{\text{ext}}$ and $T_{\text{dec}}$ for the per-operation costs:

$$\text{total} = n \cdot T_{\text{ext}} + m \cdot T_{\text{dec}}.$$

For a binary heap, both are $O(\log n)$, giving $O((n+m)\log n)$. For a Fibonacci heap, $T_{\text{dec}}$ is amortised $O(1)$ and $T_{\text{ext}}$ is amortised $O(\log n)$, giving $O(m + n \log n)$, the classic improvement, and the reason the Fibonacci heap exists in the first place. For an unsorted array with a linear scan for the minimum, $T_{\text{dec}}$ is $O(1)$ and $T_{\text{ext}}$ is $O(n)$, giving $O(n^2 + m)$.

The important observation is that the ratio $m/n$ decides which of these expressions is smallest. On a road network the average degree is a small constant, so $m$ is a small multiple of $n$; on a dense graph, $m$ approaches $n^2/2$. When $m$ is $\Theta(n^2)$, the $O(n^2)$ scan beats $O(m \log n)$ because the logarithm is pure overhead: the scan does the same asymptotic work with a sequential memory access pattern and no pointer chasing.

Decrease-key versus lazy deletion

A binary heap does not naturally support lowering a key, because finding the entry to lower requires an index from vertex to heap position. Maintaining that index costs an array of $n$ integers and an update on every swap, which is cheap per operation but touched constantly.

The alternative is to never lower a key. Push a fresh entry (newdist, vertex) on every improvement and leave the stale entry in place. At extraction time, compare the popped distance against the vertex’s current label; if the popped entry is stale, discard it and pop again.

typedef struct { int64_t d; int v; } entry;

static void push(entry *h, int *n, entry e)
{
    int i = (*n)++;
    for (h[i] = e; i > 0; ) {                 /* sift up */
        int p = (i - 1) / 2;
        if (h[p].d <= h[i].d) break;
        entry t = h[p]; h[p] = h[i]; h[i] = t;
        i = p;
    }
}

static entry pop(entry *h, int *n)             /* remove the minimum */
{
    entry top = h[0], last = h[--(*n)];
    int i = 0;
    if (*n == 0) return top;
    for (h[0] = last; ; ) {                   /* sift down */
        int l = 2 * i + 1, r = l + 1, m = i;
        if (l < *n && h[l].d < h[m].d) m = l;
        if (r < *n && h[r].d < h[m].d) m = r;
        if (m == i) break;
        entry t = h[m]; h[m] = h[i]; h[i] = t;
        i = m;
    }
    return top;
}

/* Next settled vertex, skipping entries that are stale or superseded. */
int pop_current(entry *h, int *n, const int64_t *dist, char *settled)
{
    while (*n > 0) {
        entry e = pop(h, n);
        if (settled[e.v] || e.d != dist[e.v]) continue;
        settled[e.v] = 1;
        return e.v;
    }
    return -1;
}

The heap then holds up to $m$ entries instead of $n$, so the bound becomes $O(m \log m)$ and the heap array must be sized for $m$ rather than $n$. That is a real memory cost: on a graph with a hundred million edges, an 8-byte distance plus a 4-byte vertex index per entry is over a gigabyte of transient storage if every improvement is pushed. In exchange, the code has no position index, no swap-time maintenance, and each push is a plain sift-up.

Which wins depends on how many improvements actually occur. Lazy deletion pays for a duplicate entry only when a label improves; a graph where the first label discovered for each vertex is already optimal, common when edges are processed in a good order, pays almost nothing. Decrease-key pays the index maintenance cost on every swap regardless.

Buckets when weights are small integers

If every weight is a nonnegative integer and the maximum label is bounded by some $C$, the queue can be an array of $C+1$ lists indexed by distance. Extraction scans forward from the last extracted index to the next nonempty bucket; insertion appends to bucket $d$. Each vertex enters and leaves a bucket once, and the scan pointer advances monotonically, so the total cost is $O(m + n + C)$.

This is the technique usually attributed to Dial. Its weakness is exactly its parameter: $C$ is the largest distance in the search, not the largest edge weight, so a graph with unit edges but long diameters needs a bucket per unit of distance. Two refinements address that.

The first is to exploit a small weight range rather than a small distance range. With weights in ${0, 1}$, a double-ended queue suffices: a zero-weight edge appends to the front of the current level, a one-weight edge to the back, and the queue stays sorted by construction. That is the zero-one breadth-first variant, and it runs in $O(m)$ with no heap at all. With weights in ${0, \dots, k}$ for small $k$, a circular array of $k+1$ buckets works, because labels within one round of extraction span at most $k$.

The second is a radix heap, which replaces the array of buckets with a hierarchy keyed on the binary representation of the label. Each level holds a range of keys of a fixed bit width, buckets are monotone, and a re-bucketing step redistributes a level when it is drained. The amortised cost is $O(\log C)$ per operation with a much smaller constant than a comparison heap, and the structure needs only one entry per vertex, with no duplicates. Radix heaps require integer keys and monotone extraction, both of which Dijkstra guarantees.

The monotonicity that makes buckets legal

Bucket schemes depend on a property that comparison heaps do not need: extracted keys must be nondecreasing. That holds for Dijkstra because the settled-set argument says the extracted label is final, and final labels are the true distances, which cannot decrease along a shortest path with nonnegative weights.

The dependency is worth stating because it fails in two situations that look similar. With negative weights, an extracted label can later be beaten, so keys are not monotone and the bucket scan pointer cannot advance; the algorithm is broken before the queue is. With A*, the key is $d[v] + h(v)$, and monotonicity of that key requires the heuristic to be consistent, not merely admissible; the distinction is worked through in A* and the Conditions on a Heuristic.

Choosing between the designs

The asymptotic table is not enough to pick an implementation, because the constants are large and machine-dependent. What can be said without measuring is the direction of each trade.

Dense graphs, small vertex counts, or a graph already in cache favour the array scan. Its inner loop is a linear pass over contiguous memory with a comparison, which vectorises and prefetches well, whereas a heap sift-down is a chain of dependent loads.

Sparse graphs with millions of vertices favour a heap, and the choice between decrease-key and lazy deletion is mostly a memory question: lazy deletion trades memory for simpler code and fewer writes.

Integer weights with a small range favour buckets, and the win is not asymptotic so much as structural — no comparisons at all, just index arithmetic and list splicing.

Fibonacci heaps, despite the better bound, are rarely the right answer in a standalone shortest-path routine: their constants are poor and their node layout is pointer-heavy. They matter in algorithms that perform many decrease-keys relative to extractions, which is why they appear in matching and flow codes rather than in routing codes.

Failure modes that live in the queue

Three bugs recur often enough to be worth naming.

Stale entries that are not filtered produce a vertex extracted twice. If the second extraction relaxes its edges again, the result is still correct but the work is duplicated; if the code marks the vertex settled on the first extraction and skips the second without checking the label, a genuine improvement is silently dropped.

Heap comparison that uses only the distance and not the vertex index makes output nondeterministic when labels tie, which turns a reproducible test into an intermittent one.

Bucket arrays sized by the maximum edge weight rather than the maximum distance overflow on graphs with long paths, and the overflow is an out-of-bounds write rather than a wrong answer, so it tends to be found late.

None of these change the asymptotic story, and all of them are the reason shortest-path code is worth testing against a brute-force reference on small random graphs before it is trusted on a large one.