Heaps and lazy deletion; ordered-set substitutes

Many competitive programming problems need quick access to the smallest or largest item in a changing collection. A priority queue solves this. Python's heapq module provides a min-heap: a list where the smallest item is always at index 0, and both push and pop run in logarithmic time.

Heaps in Python

A heap is a complete binary tree stored in a list where each parent is smaller than its children. When you push a new item, it goes at the end and moves up. When you pop, the smallest item is removed, the last item takes its place, and moves down. Both operations take O(log n) time.

1import heapq2
3h = []4heapq.heappush(h, 5)5heapq.heappush(h, 2)6heapq.heappush(h, 8)7heapq.heappush(h, 1)8
9print("Heap:", h)10
11while h:12    print(heapq.heappop(h), end=" ")13print()

Heap: [1, 2, 8, 5]
1 2 5 8 

The list stores the tree level by level. Index 0 is the root. Index 1 and 2 are its children. Python does this bookkeeping for you.

Max-heaps by negation

Python gives you min-heaps only. To build a max-heap, push negative values and negate them on the way out.

1import heapq2
3h = []4heapq.heappush(h, -10)5heapq.heappush(h, -3)6heapq.heappush(h, -7)7
8print("Items in descending order:")9while h:10    print(-heapq.heappop(h), end=" ")11print()

Items in descending order:
10 7 3 

Pushing -10 pushes the negated value. When it pops, negating again gives 10. The smallest negative is the largest positive.

Lazy deletion with validity checks

Sometimes an item's value improves and you want to add it to the heap again. Many textbooks update the old entry in place, but heaps are hard to search. Instead, push a new entry and skip the old one when it comes out.

Mark each item as valid or invalid. When you pop, skip invalid items until you find a valid one. This is called lazy deletionlazy deletionAn optimization technique where items are marked invalid instead of being removed immediately, with removal deferred until they are popped.In the glossary.

1import heapq2
3h = []4valid = {}5
6# Add item 0 with priority 87heapq.heappush(h, (8, 0))8valid[(8, 0)] = False9
10# Update item 0 to priority 211heapq.heappush(h, (2, 0))12valid[(2, 0)] = True13
14# Pop items, skipping invalid ones15print("Popping from heap:")16while h:17    priority, item = heapq.heappop(h)18    if valid.get((priority, item), False):19        print(f"Item {item} with priority {priority}")20    else:21        print(f"Skipping stale entry ({priority}, {item})")

Popping from heap:
Item 0 with priority 2
Skipping stale entry (8, 0)

Here, item 0 is pushed twice with different priorities. When the better one (priority 2) pops first, it is marked valid. The worse one (priority 8) is marked invalid when it pops. The skip costs one comparison per outdated item.

Maintaining a multiset with aggregates

Suppose you have a multiset and need to know the total and the count whenever someone asks. Items can be added or removed. You can store the sum and count in variables, updating them on each operation. But if you need the maximum or minimum too, a single variable does not work for those.

A lazy-deletion heap lets you simulate a balanced tree. When an item's value changes, you do not update it; you push a new entry with the new value and mark the old one invalid. When you query the maximum, you pop items until you find a valid one.

1import heapq2
3h = []4removed = set()5count = 06
7# Add items8for val in [3, 7, 2, 9, 5]:9    heapq.heappush(h, -val)10    count += 111
12print(f"Added 5 items, count = {count}")13
14# Remove item with value 915removed.add(9)16count -= 117
18# Find maximum, skipping stale entries already accounted for above19while h:20    val = -heapq.heappop(h)21    if val not in removed:22        print(f"Maximum: {val}, remaining count: {count}")23        break

Added 5 items, count = 5
Maximum: 7, remaining count: 4

Operations here are additions and removals. Removing an item drops the count once, right away, since that is when it truly leaves the multiset. The heap still holds a stale entry for it, so the query loop keeps popping and discarding entries already marked removed, without touching the count again, until it reaches one that is still current.

Sliding window minimum

Another use case is finding the minimum in a sliding window. As the window moves right, it adds one element and removes one. You could scan the window each time (O(n) per window), or use a deque with lazy deletion.

A double-ended queuedouble-ended queue (deque)A data structure that supports efficient insertion and removal at both ends, useful for sliding window problems.In the glossary is faster than a list for removing from the front. When the window includes indices 0 through 4, the deque stores indices of potential minimums in sorted order. When a new index enters, you remove indices from the back that are larger than the new one (they will never be the minimum). When the front index leaves the window, you remove it.

1from collections import deque2
3arr = [3, 1, 4, 1, 5, 9, 2, 6]4k = 35
6dq = deque()7results = []8
9for i, val in enumerate(arr):10    # Remove indices outside the window11    while dq and dq[0] < i - k + 1:12        dq.popleft()13
14    # Remove larger values from the back15    while dq and arr[dq[-1]] > val:16        dq.pop()17
18    dq.append(i)19
20    # Window is complete21    if i >= k - 1:22        results.append(arr[dq[0]])23
24print("Sliding window minima:", results)

Sliding window minima: [1, 1, 1, 1, 2, 2]

The deque keeps only indices that might become the minimum. Adding a new index and removing old ones each cost O(1) amortized because each index is added and removed once. The overall time is O(n).

Why lazy deletion works and its cost

Lazy deletion is a trade-off. Instead of immediately removing outdated entries (which would require searching the heap), you leave them and skip them when they pop. The cost of skipping is tiny: one comparison and a boolean check. The benefit is that you do not need to search or restructure the heap.

Each entry pops at most once. Even if an item's value improves ten times and you push ten entries for it, each one still pops exactly once. The total skips across all operations is at most the total pushes. If you push M times and skip K outdated entries, the total heap operations are O((M + K) log M).

For many problems, K is small. An item's value often improves a constant number of times or only once. In those cases, lazy deletion is faster and simpler than maintaining a balanced BST (which Python does not have in the standard library anyway).

Compare this to a deterministic update: you would need to find the entry in O(N) time by searching, then sift it up. Over many updates, this is slower than pushing and skipping.

A second example: tracking the best price

Imagine you are tracking the best price to buy a stock. New prices arrive one at a time. You want to quickly query the lowest price seen so far, even as old prices become outdated or no longer relevant.

You could scan all past prices each time (O(N) per query), or use a min-heap. Push each price with a timestamp. When you pop a price, check if it is still relevant (e.g., within the last K days). Skip outdated prices until you find a current one.

The min-heap gives you O(log N) per push and O(log N) amortized per query because each price is added and removed once. Without the heap, you waste time scanning old prices that are no longer relevant.

Common mistakes

A common error is forgetting to check validity or timestamp before using a value from the heap. If the item is outdated, skip it. If you use it anyway, your answer is wrong. You might get the price from a year ago instead of the current week.

Another mistake is using a recursive approach to navigate trees. Heaps are arrays, not tree structures you build manually. The indices do the navigation for you. Recursive navigation is slow and risks stack overflow on large heaps.

A third error is trying to update an entry in place. It breaks the heap invariant and produces a corrupted structure. If an entry needs a new value, push a new one and mark the old as invalid. This keeps the heap property intact.

Also, do not assume that all items in the heap are current. Once you pop an entry, mark it as used so you do not process it twice. Some problems require you to track which items you have already acted on.