Heaps with lazy deletion

A heap cannot remove an arbitrary entry cheaply: it knows where its top is and nothing else, so finding an old entry takes O(n). Lazy deletion skips the search. When a value changes, push a new entry, leave the old one where it is, and record elsewhere which entry is current. An old entry can only affect an answer once it reaches the top, so a query pops entries off the top while they are out of date and then answers. Each entry is pushed once and popped at most once, which keeps every operation at O(log n), amortised. A price board shows the problem, its brute force and the signal.

The problem: the highest and lowest price on a changing board

The updates tea 120, rice 90, tea 80, oil 150 and oil 70 give (120, 120), (120, 90), (90, 80), (150, 80) and (90, 70), as (highest, lowest). After tea drops to 80, its old price of 120 no longer counts, so the highest is rice at 90.

The brute force, and why it fails at these sizes

Keep each item’s current price in a dictionary, and after every update read every price to find the largest and the smallest. Each update costs time in proportion to the number of items on the board.

# The brute force: keep each item's current price in a dict, and scan every price after every update.


def board_by_scanning(updates):
    prices, out, looks = {}, [], 0
    for item, price in updates:
        prices[item] = price  # a new item, or a corrected price
        looks += 2 * len(prices)  # max() and min() each read every price
        out.append((max(prices.values()), min(prices.values())))
    return out, looks


updates = [("tea", 120), ("rice", 90), ("tea", 80), ("oil", 150), ("oil", 70)]
answers, looks = board_by_scanning(updates)
print(" ".join(f"({hi}, {lo})" for hi, lo in answers), f"[{looks} prices read]")

n = 200_000
print(f"at the limit, {n:,} updates of {n:,} different items: about n * n = {n * n:,} prices read")

(120, 120) (120, 90) (90, 80) (150, 80) (90, 70) [22 prices read]
at the limit, 200,000 updates of 200,000 different items: about n * n = 40,000,000,000 prices read

With 200,000 updates that each add a new item, the board grows to 200,000 items, and the two scans read about 4 × 10¹⁰ prices in all. A heap gives the largest or the smallest in O(log n), but an update must also get rid of the item’s old entry, and a heap can find that entry only by searching all of it.

What to notice

• A query reads only the top of a heap. An out-of-date entry anywhere below the top cannot change the answer.
• An out-of-date entry is easy to recognise when it does reach the top, by comparing it with the item’s current record.

So an update never has to search: it pushes the new entry and leaves the old one in place. The search happens only at the top, one entry at a time, and each out-of-date entry is thrown away once.

Lazy deletion, step by step: versions and a check at the top Pro: opens with a Pro, Premium or Ultimate pass