Lazy deletion heap
Keep stale entries in the heap; discard them when they surface.
The root is valid once stale roots are popped.
01The intuition
Start with what you would do by hand
A stock price feed sends updates with a timestamp: at time 1 the price is 10, at time 2 it is 5. Then a correction arrives: the time-1 price was really 3. After each message you must report the current maximum price. By hand you keep a small table, timestamp → latest price, and after each message scan it for the largest: {1: 10, 2: 5} → 10; after the correction {1: 3, 2: 5} → 5.
Scanning the table costs one step per timestamp, so with a million timestamps each "what is the maximum" costs a million steps. A max-heap of prices would give the maximum instantly, but a heap cannot find and remove an arbitrary entry (the old time-1 price of 10) cheaply; it only exposes its top. Corrections seem to break the heap.
Build the structure, one piece at a time
Piece one: the latest table, timestamp → latest price. This is the truth. It is a hash map, so updates and lookups are O(1).
Piece two: a max-heap of (price, timestamp) pairs. On every message, push the pair, including corrections. Do not try to remove the outdated pair. The heap now contains some entries that are stale: their price no longer matches the table.
Piece three: lazy deletion. When asked for the maximum, look at the top. Check it against the table: is latest[timestamp] equal to this price? If yes, it is the answer. If no, the entry is stale; pop it and look again. Stale entries are deleted only when they reach the top, which is the only place a heap can delete cheaply.
| Message | Table | Heap (top first) | Query for max |
|---|---|---|---|
| t=1 price 10 | {1: 10} | (10,1) | (10,1) matches: 10 |
| t=2 price 5 | {1: 10, 2: 5} | (10,1), (5,2) | (10,1) matches: 10 |
| t=1 price 3 (correction) | {1: 3, 2: 5} | (10,1), (5,2), (3,1) | (10,1) stale, pop; (5,2) matches: 5 |
| t=2 price 1 | {1: 3, 2: 1} | (5,2), (3,1), (1,2) | (5,2) stale, pop; (3,1) matches: 3 |
Why it is correct
Every current (price, timestamp) pair was pushed into the heap when it became current, and it stays there until popped. An entry is popped only after being found stale, so no current entry is ever removed. Therefore the heap always contains every current pair, plus some stale ones.
max over current pairs = the first heap entry from the top whose price equals latest[timestamp]
The top of the heap is the largest price among all entries. If it is current it is the largest current price, since current entries are a subset. If it is stale, removing it cannot affect the answer, and we look again. The loop ends because the heap is finite and contains at least one current entry whenever the table is non-empty.
Why it is fast
Each message does one map write and one heap push, O(log m) where m is the number of messages so far. A query may pop several stale entries, but each entry is pushed once and popped at most once in its whole life, so across all queries the pops total at most the number of pushes. Spread over the messages, that is O(log m) per message on average, which is what "amortised" means. The by-hand scan was O(n) per query. The cost is memory: stale entries sit in the heap until they surface, so the heap can hold all m messages rather than just the live timestamps.
How to recognise it in an interview
You need the maximum or minimum of a changing set, and the changes include updates or removals of specific elements, not only insertions: "price corrections", "the number of seats freed", "remove an element from the window". Say: "I will push every update into the heap and verify the top against a map of the truth, popping stale entries lazily." Stock Price Fluctuation is this exactly, with a max-heap and a min-heap side by side. Sliding Window Median uses two heaps with lazy removal of elements that have left the window. Design a Number Container System keeps a min-heap of indices per number and discards an index whose current number no longer matches.
02The idea in one line
Keep stale entries in the heap; discard them when they surface.
Reach for it when: Sliding window median, stock price fluctuation, number of visible, exam rooms.
Cost: O(log n) amortised.
03The walk-through, step by step
The video works one example: Stock Price Fluctuation with corrected timestamps. These are its captions in order, so you can follow without the video or check a step you missed.
- Corrections make heap entries stale; leave them and skip when they surface
- Update t=1 to 10: record latest, push (10,1)
- Update t=2 to 5: record latest, push (5,2)
- Top (10,1) matches latest: maximum = 10
- Update t=1 to 3: record latest, push (3,1) — the old entry stays
- Top (10,1) is stale: latest[1] is 3, pop it
- Top (5,2) matches latest: maximum = 5
- Update t=2 to 1: record latest, push (1,2) — the old entry stays
- Top (5,2) is stale: latest[2] is 1, pop it
- Top (3,1) matches latest: maximum = 3
- Each entry is pushed once and popped at most once: O(log n) amortised
04Asked at Google
5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Design a Number Container System | Medium | 31 | |
| Sliding Window Median | Hard | 30 | |
| Stock Price Fluctuation | Medium | 26 | last 6 months |
| Exam Room | Medium | 21 | |
| Most Beautiful Item for Each Query | Medium | 6 |
05Related patterns
Other patterns in Heap: Top-k with a size-k heap, Two heaps (running median), K-way merge, Greedy scheduling with a heap, Pop-k-then-rebuild (frequency greedy).