Heap with Lazy Deletion

Ranking designs ask for "the highest-rated item right now" while ratings keep changing. A heap gives you the best item fast, but it can't remove or update an item in the middle. Lazy deletion gets around that: never fix the heap in place. Push the new value, leave the old one behind, and throw away stale entries only when they reach the top.

The idea#

Keep two structures with clear roles:

A dict is the source of truth: item -> current score.
The heap is only an index for ranking. It may contain old, stale entries.

On an update, write the dict and push (-score, item). On a read, look at the top. If its score disagrees with the dict, it is stale: pop it and look again. Use a while, because several stale entries can sit on top in a row.

Why it is fast: every entry is pushed once and popped at most once in its whole lifetime. A read that pops many stale entries is paying for earlier updates, so the amortized cost per operation stays $O(\log n)$ .

Why memory needs care: an item updated 1,000 times leaves 999 stale entries. A compaction step rebuilds the heap from the dict when stale entries outnumber live ones.

How to spot it#

These cues point to a heap with lazy deletion.

"return the highest / lowest current X" with updates in between
"change rating", "update price", "correct a past record"
ties broken by name or id (put the tie-breaker in the tuple)
"merge the newest items from k sources" (k-way merge)
"assign the smallest available id" after deletions

Template#

Here is a lazy max-heap keyed by name, with the tie-break in the tuple and a compaction step.

init():
    score = empty dict                # name -> current score (the truth)
    heap = empty list                 # (-score, name): ties by name
set(name, new_score):
    score[name] = new_score
    push (-new_score, name) onto heap # the old entry goes stale
    if heap size > 2 * number of names:
        rebuild heap from score; heapify   # compaction: O(n)
best():
    while heap is not empty:          # while: several stale tops in a row
        neg, name = top of heap
        if score[name] == -neg: return name
        pop the top                   # each stale entry is popped once
    return nothing

Negating the score turns Python's min-heap into a max-heap. Tuples compare field by field, so (-10, "apple") < (-10, "banana"): equal ratings fall back to the alphabetically smaller name.

K-way merge with tombstones#

The same "skip what no longer counts" idea works when a heap merges several sources. Some feeds are a merge of k sorted lists, each oldest first. Seed the heap with only the newest item from each list.

Pop the newest overall, then refill from the same list's next-older item. Deleted items go in a tombstone set (a record of what was deleted, while the item stays in its list) and are skipped during the merge. Think of a race where you only watch the runner at the front of each lane.

heap = (-time, id, list u, index i) for the newest item of each list
heapify heap
feed = empty list
while heap is not empty and feed has fewer than k items:
    pop (time, id, u, i)
    if id is not in deleted: append id to feed   # tombstone: skip
    if i > 0:                                    # refill from lane u
        push the item at index i - 1 of list u
return feed

Tombstones mean the lists never shrink and indexes never shift, so a reader in the middle of a merge can't hit a missing index.

Pitfalls#

These mistakes cause the most wrong answers.

Updating the heap but not the dict (or the reverse). The dict decides what is stale.
if instead of while on read. Two stale entries on top in a row return a wrong answer.
Sign errors in a max-heap. Push -score and compare against -neg when reading back.
Unbounded stale buildup. Rebuild from the dict when the heap grows past a multiple of the live size.
Un-orderable payloads in tuples. If two scores tie, Python compares the next field. Put a comparable tie-breaker (name, id, index) before any object that can't be compared.
Copying every list for a top-k feed. Merge from the heads; only touch what the answer needs.
Assuming you need a heap. If keys arrive already sorted, a deque with the same stale check is enough.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the Food Rating System.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Design a Food Rating System

Keep one lazy heap per cuisine of (-rating, food), plus food -> cuisine so an update knows which heap to push into. Before finishing, check that the dict and the heap are both updated, ties sort by name, and the read uses while.

Hint: Design a Food Rating System: other versions

Scanning the cuisine's foods is $O(1)$ to change and $O(n)$ to read, with one pass and no sort. A SortedSet per cuisine (from sortedcontainers) is $O(\log n)$ for both: remove the old tuple, add the new one. The lazy heap needs only the standard library, but memory is $O(n + \text{updates})$ until compaction.

Hint: Design a Food Rating System: SortedSet cost

Quote SortedSet[0] as $O(\log n)$ , not $O(1)$ . sortedcontainers stores a list of sublists plus a positional index and documents indexing as $O(\log n)$ . Index 0 and -1 take a shortcut in the current implementation, but that is a detail, not the contract.

Hint: Design Twitter

Don't copy every followee's tweets into one list: following 500 users with 1,000 tweets each touches about 500,000 tweets per feed. A k-way merge touches about 510: one seed per followee plus at most 10 refills, so $O(K + 10 \log K)$ with heapify. Handle deletes with a deleted_tweets tombstone set.

Hint: Design Twitter: scale

With append-only lists and tombstones, readers don't need a lock. At production scale the merge runs over per-user timelines held in a cache layer such as Redis.

Hint: Design Video Sharing Platform

"Reuse the smallest freed id" is a pool, not a ranking, but it is the same heap. Keep a min-heap of freed ids plus a next_id counter: upload pops the heap if it has anything, otherwise takes next_id; remove pushes the id back. A SortedSet also works, but its pop() removes the largest item, which forces negated ids.

Hint: Design Video Sharing Platform: follow-ups

Small, dense ids give denser B-tree indexes and better cache locality, and they stay inside fixed-width id types. Many real systems never reuse ids, so old references and audit logs stay unambiguous. At scale, keep video bytes in blob storage (such as S3) and metadata in the database, serve through a CDN, use atomic increments (Redis INCR) or batching for view counts, and use Snowflake-style ids or UUIDs across servers.

Hint: Stock Price Fluctuation

Prices for a timestamp can be corrected later. Keep timestamp -> price as the truth, plus a max-heap and a min-heap of (price, timestamp). For the maximum or minimum, pop while the top's price no longer matches the dict for its timestamp.

Hint: Design Authentication Manager

You don't need the heap. Every expiry is now + ttl with now only increasing, so expiries arrive sorted. A deque with the same tombstone check is enough, with $O(1)$ appends; see Sliding Time Window.

Key takeaways#

The dict is the truth and the heap is an index; stale heap entries are fine as long as reads check them.
Each entry is pushed once and popped once, so lazy deletion is amortized $O(\log n)$ .
Compact (rebuild from the dict) when stale entries pile up.
Put the tie-breaker in the tuple: (-rating, name).
For top-k across k sorted sources, seed with each head and refill from the source you popped.
A min-heap of freed ids plus a counter gives "smallest available id" without extra packages.

Core idea#

A heap cannot update an item in the middle. Keep a dict as the source of truth, push every new value into the heap, and discard stale tops on read.

Key points#

On update: write the dict, then push (-score, item).
On read: pop while the top disagrees with the dict. Use while, not if.
Each entry is pushed once and popped once, so the cost is amortized $O(\log n)$ .
Compaction: rebuild the heap from the dict when stale entries outnumber live ones.
Put the tie-breaker in the tuple: (-rating, name).
K-way merge (Design Twitter): seed with each source's newest item, then refill from the source you popped. Skip deleted ids with a tombstone set.
Smallest available id: a min-heap of freed ids plus a next_id counter.
Sorted arrivals (Authentication Manager) need only a deque.

Food Rating options#

Approach	`changeRating`	`highestRated`
Scan the cuisine	$O(1)$	$O(n)$
`SortedSet` of `(-rating, food)`	$O(\log n)$	$O(\log n)$
Heap + lazy deletion	$O(\log n)$	amortized $O(\log n)$

With one heap per cuisine, you also need food -> cuisine, so an update knows which heap to push into.

Template#

set(name, new_score):
    score[name] = new_score               # the dict is the truth
    push (-new_score, name) onto heap     # old entry goes stale
best():
    while heap is not empty:
        neg, name = top of heap
        if score[name] == -neg: return name
        pop the top                       # stale entry
    return nothing

Pitfalls#

Updating the heap but not the dict, or the reverse.
if instead of while on read.
Sign errors. Push -score and compare against -neg.
Unbounded stale buildup without compaction.
Un-orderable payloads in tuples. Put a comparable tie-breaker first.

Say it in an interview#

"The dict is the truth. The heap is only an index, and reads skip stale tops."
"A feed merges from each list's head instead of copying every tweet."