skip to content

A standard-library priority queue has no decrease-key — how do you change a queued item's priority?

level: middleimportance: must knowfreq 62%

answer

  1. only the top of a heap is addressable
  2. so the update operation is simply absent
  3. insert a new entry instead of editing
  4. old entries linger and must be recognised
  5. version counter checked on every pop

basics

~20 s

Standard-library priority queues expose no decrease-key. Push a fresh entry at the new priority and discard outdated entries when they surface at the top. Mutating a stored key in place does not re-sift the heap and silently corrupts its order.

solid answer

~60 s

Standard priority queues offer insert, inspect-top and extract-top and nothing else, because updating an element's priority would require the container to hand out a stable handle to every element it holds — a cost paid by every user, most of whom never update anything. So you emulate it lazily: push a *new* entry carrying the new priority, leave the old one in the queue, and on extraction check whether the entry you popped is still current — via a version counter or a best-known-value table — skipping it if it is not. The queue then holds up to one entry per update rather than one per item, so memory and the number of pops grow with updates; each skip is O(log n) and the total stays in the same asymptotic class. What you must not do is mutate the priority field of an item already inside the queue: nothing re-sifts it, so it sits in a position the ordering no longer justifies and extraction starts returning the wrong item.

code

pseudocode · 11 lines
pseudocode
// changing an item's priority: never edit the queued entry
version[id] = version[id] + 1
push(pq, (new_priority, version[id], id))

// extraction tolerates the leftovers
while not empty(pq)
    (p, v, id) = extract_top(pq)
    if v != version[id]
        continue              // superseded entry, discard it
    serve(id, p)
    ...

go deeper

for a junior

Remember that a priority queue lets you push, look at the top and take the top — nothing else. Changing the priority of something already queued is not an operation you have, so you push a fresh entry instead.

for a middle

Explain the workaround end to end: push a new entry, keep a version counter or best-value table on the side, and skip outdated entries as they surface. Be able to say why editing a queued item in place reorders nothing.

for a senior

Talk about the cost you took on: the queue now grows with updates rather than items, discards arrive in bursts that widen tail latency, and a long-lived scheduler may need per-tick coalescing or a bottom-up rebuild over live entries.

for a principal

Decide when the workaround stops being acceptable for the system. Weigh the extra memory across a fleet and the burstiness against the maintenance cost of a bespoke structure, and set a measured threshold rather than reaching for cleverness up front.

## The operation that is missing Textbook priority queues list four operations: insert, inspect the top, extract the top, and **decrease-key** — change the priority of an element already in the queue and restore the ordering. The classic analyses of shortest-path and minimum-spanning-tree algorithms are written against that fourth operation. Standard-library priority queues almost universally offer the first three and not the fourth. That is an interface decision, not an oversight. To change one element's priority the container must first *find* it, and a heap can address only its top: the parent-child relation says a parent beats its children, and nothing more, so an arbitrary element is not locatable in better than linear time. Making it locatable means every element carries a stable handle back into the container, which every user pays for in memory and interface surface — including the large majority who only ever push and pop. ## What people try first, and why it corrupts the queue The instinct is to keep a reference to the queued item and assign a new value to its priority field. The item is now sitting at a position the ordering no longer justifies, and **nothing re-sifts it** — the queue is not notified and has no hook to be notified. The invariant is broken silently. Extraction then returns whatever happens to be on top, which may not be the best item; nothing throws, nothing is lost, the order is just wrong, and the symptom appears far from the mutation. This is the single most common priority-queue bug in production code, and it survives review because the mutating line looks innocuous. ## The lazy-entry workaround The portable emulation is to treat entries as immutable snapshots: 1. When an item's priority changes, **push a new entry** with the new priority. Do not touch the old one. 2. Keep a side record of what is current — a per-item version counter, or a table of the best value seen so far. 3. On extraction, compare the popped entry against that record. If it is outdated, **discard it and pop again**; otherwise process it. The queue therefore contains stale duplicates, and correctness rests on one invariant: for any item, exactly one queued entry matches the side record, so the item is processed exactly once and always at its current priority. ## What it costs - **Space.** The queue holds up to one entry per *update*, not per distinct item. A workload that revises priorities heavily grows a queue much larger than its item count, and that memory is live until the stale entries are popped. - **Time.** Every stale entry still costs an O(log n) extraction to discard. The work is bounded by the number of pushes, so on graph-shaped workloads with E updates the total remains O(E log E), the same asymptotic class as the decrease-key formulation — the constant and the peak memory are what change. - **Latency shape.** Discards arrive in bursts. A scheduler can pop several stale entries in a row before finding live work, so a per-pop latency budget must account for the skip loop, not just one extraction. ## Guarding the skip loop The guard has to be cheap and total. A monotonically increasing version per item is the simplest: the entry carries the version it was pushed with, and a pop is live only when that version matches the item's current one. A best-known-value table works the same way for cost-minimising searches: if the popped entry's value is worse than the recorded best, it has been superseded. Both are O(1) checks. What does not work is checking membership in the queue itself — that is a linear scan. ## Bounding the growth If updates vastly outnumber items, the stale backlog is worth watching. Practical mitigations, in the order you should reach for them: cap how often a single item may be re-pushed; coalesce updates within a tick so one item enqueues once per tick rather than per event; and, when the backlog is dominated by entries you know are dead, rebuild the queue from the live entries in a single bottom-up pass, which is O(n) rather than n removals. Measure before you do any of this — for most workloads the stale entries are a small multiple of the item count and the simple version guard is the whole solution. ## What to say in an interview Say that the operation is missing, say *why* it is missing (elements are not addressable), describe the push-new-plus-skip-stale pattern with its guard, and name the cost honestly: more memory and more pops, same asymptotic class. Then add the warning that carries the most weight — mutating a queued item's priority in place does not reorder anything and is a silent corruption, not an error.

  • How do you know, at extraction time, that the entry you just popped is stale?
    Carry the deciding fact in the entry and compare it against a side record in O(1). A per-item version counter is the general form: the entry stores the version it was pushed with, and it is live only if that still matches. For cost-minimising searches, a table of the best value seen so far serves the same purpose.
  • Does the lazy approach change the asymptotic cost of a shortest-path style search?
    Not the class. Each update pushes one entry, so the queue holds O(E) entries and every push and pop is O(log E), giving O(E log E) overall — equivalent to O(E log V). What changes is peak memory and the constant factor, since stale entries occupy space and each costs a full extraction to discard.
  • When does the stale backlog become a real problem rather than a constant factor?
    When updates vastly outnumber items and the queue must live for a long time — a long-running scheduler revising the same few items thousands of times. Then cap or coalesce updates per tick, or rebuild the queue from live entries in one bottom-up O(n) pass. Measure first; usually the backlog is a small multiple of the item count.

It is like a paper ticket queue with no way to edit a ticket: you hand out a new ticket at the new priority and tear up the old one when it finally reaches the window.

saying these in an interview costs you the question

  • Assigns a new priority to an item already in the queue
  • Believes the queue re-sorts itself when a field changes
  • Says stale entries make the algorithm asymptotically worse
  • Checks staleness by searching the queue for the item
  • Claims mutating a key throws an error you would notice

context

resolving links…