A review shows a priority queue's arbitrary-element removal called in a loop — what do you flag?
answer
- a heap makes only its top addressable
- two steps: find it, then repair
- which of those two dominates
- now multiply that by the loop count
- mark cancelled, skip on extraction
basics
~20 sRemoving a named element from a heap-backed queue is O(n): only the top is addressable, so the element must be found by scanning. Called once per cancelled item in a loop, that is quadratic work hidden behind an innocuous-looking call.
solid answer
~50 sArbitrary removal on a heap-backed priority queue is two steps: locate the element, then repair the hole. The repair is the cheap part — move the last element in and sift it up or down, O(log n). Locating it is a linear scan, because heap order only relates parents to children and gives no index by value, so removal is O(n). In the loop under review, cancelling k of n queued items therefore costs O(k·n), which is quadratic when cancellations scale with the queue — a scheduler that was fine in testing collapses under a burst. The fix is to stop removing eagerly: record the cancelled identifiers in a set and discard them when they surface at the top, which is O(1) per cancellation, or, if most of the queue is dead, rebuild from the survivors in one bottom-up pass at O(n). I would also ask what removal-by-value does about duplicates, since it typically removes only the first match.
code
pseudocode · 9 lines// pq: priority queue of queued packets, size n
// cancelled: packets whose flow was torn down this tick, size k
for i in 0..length(cancelled)-1
remove_element(pq, cancelled[i])
while not empty(pq)
p = extract_top(pq)
transmit(p)
...go deeper
Know the cost table for a heap-backed priority queue: top is O(1), insert and extract are O(log n), and finding or removing a named element is O(n) because only the top is addressable.
Explain the two phases of arbitrary removal and which one dominates, then multiply by the loop: k removals over n queued items is O(k·n), which becomes quadratic when cancellations scale with the queue.
Show the review judgment. Name the workload that triggers the blow-up, propose lazy cancellation with a skip on extraction as the O(1) alternative, and flag the duplicate-match hazard in removal by value.
Own the standard. Decide whether cancellation is a supported concept in your scheduling layer at all, and make the pattern — mark and skip, with a bounded marker set — the house default so this diff never has to be caught by review again.
## Why removal is the expensive operation on a heap A binary heap gives one guarantee: every parent compares favourably against its children. That is a *partial* order. It tells you where the best element is — the top — and nothing at all about where any other element lives. There is no mapping from a value to a position. So removing an element you can name is two operations glued together: 1. **Find it.** With no value-to-position mapping, this is a scan over the stored elements, comparing by identity or equality: O(n). 2. **Repair the hole.** Move the last element into the vacated slot and sift it up or down until the parent-child relation holds again: O(log n). Step 2 is the part everyone remembers and it is not the problem. Step 1 dominates, and removal is O(n). ## The loop in the diff The scheduler holds n queued packets. Each tick, k flows are torn down and the code calls removal once per cancelled packet. Total cost is O(k·n) plus O(k log n) for the repairs — and when k grows with n, as it does when a burst of flows dies at once, that is **quadratic**. This is the classic shape of a service that passes load tests at a hundred queued items and falls over at ten thousand: the per-call cost is invisible at the call site, and the loop looks like ordinary cleanup. A second, quieter defect lives in the same line. Removal by value normally removes **one** matching element — the first one found. If the queue can hold duplicates, or two distinct entries compare equal under the ordering rule, the call may remove an element you did not mean and leave the one you did. That produces a packet that is never cancelled and one that vanishes, which is far harder to diagnose than a latency problem. ## What to suggest instead **Lazy cancellation (usually the right answer).** Keep a set of cancelled identifiers. Cancelling is O(1) — you touch a set, not the queue. On extraction, check the popped entry against the set and, if it is cancelled, discard it and pop again. Each dead entry still costs one O(log n) extraction, but you pay that once, at the moment it would have surfaced anyway, instead of paying a full scan per cancellation. Remember to drop identifiers from the set once their entry has surfaced, or the set becomes the leak the queue was not. **Bulk rebuild (when most of the queue is dead).** If a tick invalidates a large fraction of the queue, filter the stored elements once and build a new queue bottom-up. Building from n elements is O(n) — cheaper than n·log n reinsertions and dramatically cheaper than k linear scans. **Leave it alone (sometimes correct).** If the queue holds a few dozen entries and cancellations are rare, an O(n) scan is a handful of comparisons and the eager removal keeps the code obvious. The review comment is then about bounding the queue, not about the algorithm. ## How to frame the review comment Name the cost, name the input that triggers it, and offer the smallest fix. "Removal here scans the whole queue to find the element, so this loop is O(k·n); when a burst tears down most flows at once that is quadratic. A cancelled-set plus a skip on extraction makes cancellation O(1) and costs one discard per dead entry." That is more persuasive than an abstract complaint about complexity, because it names the workload — a burst — under which the code actually breaks. ## The costs worth memorising | Operation on a heap-backed queue | Cost | |---|---| | Inspect the top | O(1) | | Insert | O(log n) | | Extract the top | O(log n) | | Build from n existing elements | O(n) | | Find or remove a named element | O(n) | The last row is the one candidates forget, and it is the row that turns a correct scheduler into a quadratic one.
- If the repair after removal is only O(log n), why is the whole operation O(n)?Because the repair cannot start until the element is located, and a heap offers no mapping from value to position — only the top is addressable. Finding the element is a scan over all stored elements, O(n), which dominates the O(log n) sift that follows. The cheap half is the half everyone quotes.
- When would you rebuild the queue instead of skipping cancelled entries on extraction?When a large fraction of the queue is dead at once. Filtering the survivors and building bottom-up is O(n) total, versus one discard extraction per dead entry spread over the future. Rebuilding also releases the memory immediately, which matters if the dead entries hold payloads rather than identifiers.
- What is the risk of removal-by-value when the queue can contain duplicates?It typically removes the first matching element it finds, not the specific instance you hold. With duplicates, or with entries that compare equal under the ordering rule, you can delete the wrong one — leaving the intended target queued and dropping a live item. Identity-based bookkeeping avoids the ambiguity entirely.
saying these in an interview costs you the question
- Calls arbitrary removal O(log n) like the other operations
- Thinks the queue keeps an index from value to position
- Assumes removal takes out every matching duplicate
- Reinserts survivors one by one instead of building bottom-up
- Dismisses the loop as fine because each call looks cheap