Heaps and Priority Queues in Order Book Implementations

A heap answers best bid and offer cleanly until cancellation, staleness or a tie exposes what it cannot do inside an order book.

Heaps and priority queues are the first structure most candidates reach for when asked to track the best bid and the best offer, and they are also the structure whose limitations the interviewer wants explained once the follow-up removes the assumption that only the best price ever changes. Four variants recur: the naive best-bid best-offer heap and why cancellation breaks it, consolidating a top-of-book view across several venues, keeping only the best N price levels under constant turnover, and ordering a matching engine's events by timestamp with a priority queue.

State the problem precisely: maintain the current best bid and best offer as orders arrive, and support querying either in constant time. A max-heap ordered by price answers the best bid query in O(1), with insertion in O(log n), and a mirrored min-heap answers the best offer the same way, which is why this is usually the first structure a candidate proposes and is a reasonable opening answer.

The gap appears the moment cancellation enters the story, since a standard heap has no efficient way to remove an arbitrary element that is not at the top, only the top itself. Most candidates propose lazy deletion, marking a cancelled order as invalid in a side hash set and simply skipping it when it is eventually popped off the top, which works but leaves stale entries sitting in the heap and defers the real cost of a cancel rather than paying it up front, a tradeoff worth stating rather than hiding.

State the problem precisely: given the current best bid and offer from each of several venues, maintain a single consolidated best bid and offer across all of them as any individual venue's quote updates. A min-heap keyed on offer price and a max-heap keyed on bid price, each holding one entry per venue, answer the consolidated query in O(1) with an update costing O(log v) for v venues, since only the one venue that changed needs to be removed and reinserted.

The follow-up asks how to detect that a venue has gone stale, meaning it stopped publishing updates rather than genuinely holding its price, since a heap by itself cannot distinguish a quiet venue from a genuinely unchanged one. The expected answer pairs the heap with a per-venue last-update timestamp checked on a timer, evicting a venue's quote from consideration once its age crosses a threshold, which is a detail the naive heap-only design silently misses.