Data Structures & Algorithms / Ordered structures and graph reasoning / Lesson 9

Heaps, priorities, and streaming top-k

Use the heap invariant for extremum access and keep tie-breaking, replacement, and stale entries explicit.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

A heap orders parents, not the entire array
Keep the weakest retained candidate at the root
Use a deterministic tie-breaker for opaque records

A heap orders parents, not the entire array

A binary min-heap keeps every parent no greater than its children, making the root minimal. It does not keep siblings or arbitrary array positions globally sorted. For zero-based storage, children of i occur at 2*i+1 and 2*i+2 when those positions exist. Python3.12 heapq operates on ordinary lists using this min-heap contract. Read heap[0] for the minimum, and pop to remove it while restoring the invariant. Iterating the backing list is not a sorted traversal. If ordered output is required, repeated popping or a separate sort adds work that belongs in the contract.

Keep the weakest retained candidate at the root

For the largest k values seen so far, maintain a min-heap of at most k retained values. Once full, its root is the smallest retained candidate. A new value no larger than the root cannot improve the selected multiset; a larger one replaces that weakest candidate. The first program returns the retained values sorted descending for presentation, adding O(k log k) final sorting. Processing n inputs costs O(n log k) in the usual bounded-comparison model for k>=2, with O(k) retained space. For k=0 the explicit result is empty, and negative k is rejected.

python Self-contained Python3 algorithm example using synthetic local data.

import heapq

def largest_k(values, k):
    if k < 0:
        raise ValueError("k must be nonnegative")
    if k == 0:
        return []
    heap = []
    for value in values:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif value > heap[0]:
            heapq.heapreplace(heap, value)
    return sorted(heap, reverse=True)

print(largest_k([4, 1, 9, 9, 3], 3))
print(largest_k([4, 1], 0))

Expected output

[9, 9, 4]
[]

Duplicates count as distinct input occurrences. heapreplace is used only after the candidate is proved better than the current root.

Use a deterministic tie-breaker for opaque records

A tuple heap compares later fields when priorities tie. If the payload is an ordinary dictionary or a custom non-orderable object, that fallback can raise TypeError. The second program places a unique arrival counter between priority and payload. Equal priorities then follow arrival order without comparing the dictionaries. This is a declared scheduling policy, not an intrinsic promise of every priority queue. Do not reuse counters among live entries. Choose priority direction and tie policy explicitly, especially when a domain requires fairness or a reproducible result rather than arbitrary equal-priority removal.

python Self-contained Python3 algorithm example using synthetic local data.

import heapq
from itertools import count

arrivals = count()
heap = []
for priority, name in [(2, "Maps"), (1, "Rivers"), (2, "Atlas")]:
    heapq.heappush(heap, (priority, next(arrivals), {"name": name}))
order = []
while heap:
    _, _, payload = heapq.heappop(heap)
    order.append(payload["name"])
print(order)

Expected output

['Rivers', 'Maps', 'Atlas']

Priority1 leaves before priority2; Maps precedes Atlas because its tie-break counter is smaller.

Replacement operations have different semantics

heapreplace removes the current minimum and inserts a new value even if the new value is smaller. heappushpop logically inserts first and then removes the minimum. They are not interchangeable without proving the surrounding condition. Likewise, heapify builds the invariant in linear time rather than repeatedly sorting the whole input. Individual push and pop require logarithmic repair in heap size, while reading the root is constant-time. Include comparison cost and the actual live heap size in analysis. A priority queue containing stale duplicates may be larger than the number of current domain items.

Priority changes require a consistency policy

Changing a record’s priority while it sits inside the backing list can break heap order. A standard approach is to insert a new version and mark the previous version obsolete using an external authoritative map. On pop, skip an entry whose stored version or priority no longer matches that map. This lazy-deletion policy is useful in shortest-path algorithms, but stale entries consume memory until removed. If arbitrary deletions and bounded memory are essential, an indexed heap or another structure may be more suitable. The data structure choice must include the full update contract, not just extraction speed.

Compare retained results with a trusted small reference

For tiny inputs, compare largest_k with sorted(values,reverse=True)[:k] for every k from zero through values longer than the sequence. Include duplicate maxima, negative numbers, and empty input. Verify the source list is unchanged and the output multiplicity is preserved. For priority records, test equal priorities with unorderable payloads and confirm the declared arrival policy. Do not compare internal heap-array order with a sorted list; inspect the heap property or the sequence of popped values. These local tests need no real scheduler, concurrent service, or load generator.

Common errors and fixes

A heap array is displayed as sorted output

Why it happens: Parent-child order was mistaken for global order.
How to fix it: Pop in priority order or explicitly sort a copy when required.
Prevent it next time: Test a heap with several siblings.

Equal priorities raise TypeError

Why it happens: Tuple comparison reached non-orderable payloads.
How to fix it: Insert a unique tie-break field before the payload.
Prevent it next time: Use equal-priority dictionary payload fixtures.

A smaller candidate evicts a useful top-k value

Why it happens: heapreplace was called without checking improvement.
How to fix it: Guard replacement or use a proven push-pop policy.
Prevent it next time: Test incoming values below the retained minimum.

Check your understanding

1. Why does the top-k heap keep the smallest retained value at its root?

Show worked solution

That value is the threshold a new candidate must beat. A min-heap makes testing and replacing the weakest retained occurrence efficient while preserving all larger candidates. A max-heap would expose the strongest candidate instead, which does not answer this replacement question directly.

2. Does adding a tie-break counter make priorities fair automatically?