For a stream x1..xn with a total ordering key(x), retain the largest k. A min-heap H of capacity k contains exactly the largest min(k,i) items after prefix i. Reverse the boundary for the smallest k.
Recognition signals
Only a kth value or the best k items are needed; the remaining order is irrelevant.
Items arrive online and the answer must be refreshed incrementally.
A new item can be admitted by comparing it with the weakest retained item.
k is much smaller than n, so a full O(n log n) sort is wasteful.
Records have composite ranking keys but only a fixed-size leaderboard survives.
False friends
Signal
Why it is different
One offline kth query
When mutation is acceptable, Quickselect offers expected O(n); the heap pays log k for streaming, predictable behavior, and input preservation.
A single sliding-window extreme
A monotonic deque is usually linear and expires elements directly; a heap needs lazy stale-entry removal.
The complete sorted order is required
A heap exposes a boundary, not a total order. Sorting everything is clearer when every rank is consumed.
Core invariant
After every input prefix, the heap contains the best at most k candidates from that prefix, and its root is the retained candidate most eligible for eviction.
State, transition, and processing order
Item
Definition
State
A capacity-k heap whose entry carries a ranking key, a stable tie-breaker, and the original object.
Transition
Push while under capacity. Once full, replace the root only when the new entry is better; otherwise discard it.
Frontier / order
The source is scanned in arbitrary order. The root is the current admission boundary; sort only the final k items if presentation order matters.
Python skeleton
from heapq import heappush, heapreplace
def top_k(items, k, key=lambda x: x):
if k <= 0:
return []
heap = []
for serial, item in enumerate(items):
entry = (key(item), serial, item)
if len(heap) < k:
heappush(heap, entry)
elif entry[:2] > heap[0][:2]:
heapreplace(heap, entry)
return [item for _, _, item in sorted(heap, reverse=True)]
Correctness sketch
The invariant holds for the empty prefix.
Before capacity, every seen item belongs. At capacity, an item no better than the root cannot enter the prefix Top-K; a better item can only displace that weakest member.
Induction over all items proves exact membership. The final sort changes order, not membership.
Complexity
Time
Space
Parameters
O(n log k), plus O(k log k) for ordered output
O(k)
n is the item count and k is the retention limit.
Edge cases
k <= 0
k >= n
equal keys with non-orderable objects
reversing the heap for bottom-k
NaN or keys without a total order
Error patterns
Pattern
Why it fails / fix
Using the wrong heap direction
Largest-k needs a min-heap so the weakest retained item is exposed; smallest-k needs the symmetric maximum boundary.
Letting Python compare payloads
Equal tuple prefixes reach the object field. Add a monotone serial tie-breaker before the payload.
Treating heap storage as sorted
Only the root has a rank guarantee; explicitly sort the retained k items when needed.
Push-pop for every rejected item
Compare with the boundary first and use heapreplace only for admitted candidates.
Selection and exclusion rules
Prefer a bounded heap for streaming input or k much smaller than n.
Compare with Quickselect for one offline rank query on mutable data.
Use a full sort when every rank is eventually consumed.
For window Top-1, test whether a monotonic deque fits first.