4.17.0 — Heap & Priority Queue: The Pattern

Recognition cue. The problem says top k, k-th largest or smallest, median of a stream, merge k sorted things, or a loop repeatedly needs "the current largest or smallest" from a changing collection.

The move. A heap gives the extreme element in O(1) and inserts or removes in O(\log n). It does not keep everything sorted — it only guarantees the root, and that weaker promise is what makes it cheap.

The rule that decides min or max

People get this backwards constantly, so hold on to one sentence:

The root must be the item you are about to throw away.

• k largest → min-heap of size k. The root is the weakest keeper, the one a better arrival replaces.
• k smallest → max-heap of size k. The root is the worst keeper.

The three shapes

# 1. SIZE-K HEAP — top k, and the only version that works on a stream
heap = []
for x in items:
    heapq.heappush(heap, x)          # min-heap → keeps the k LARGEST
    if len(heap) > k:
        heapq.heappop(heap)
# heap[0] is the k-th largest

# 2. K-WAY MERGE — one candidate per source
for i, src in enumerate(sources):
    heapq.heappush(heap, (src[0], i, 0))
while heap:
    val, i, j = heapq.heappop(heap)
    ...
    if j + 1 < len(sources[i]):
        heapq.heappush(heap, (sources[i][j+1], i, j+1))

# 3. TWO HEAPS — the middle of a stream
small = []   # max-heap (negated), lower half
large = []   # min-heap, upper half

Python specifics worth knowing

heapq is min-only. For a max-heap, negate on the way in and on the way out. Forgetting one of the two is the standard bug.

heapify is O(n), not O(n \log n). Building in place by sifting down from the middle beats n separate pushes.

Push tuples for tie-breaking. (priority, index, item) — without a comparable second field, Python compares the third element, and objects without < raise TypeError. This bites in 4.9.10 Merge K Sorted Lists.

heapq.nlargest(k, xs) and nsmallest use a size-k heap internally. Know them, and know what they are doing.

JavaScript has no built-in heap. Write one, or use pairwise merging instead (4.9.10).

The seven problems

#	Problem	The one insight
4.17.1	Kth Largest in a Stream	Keep only k; the rest can never return
4.17.2	Last Stone Weight	The collection changes, so sorting will not do
4.17.3	K Closest Points to Origin	Compare squared distances; max-heap for the k smallest
4.17.4	Kth Largest in an Array	Quickselect is O(n) because it recurses into one side
4.17.5	Task Scheduler	Run the most frequent task; or use the skeleton formula
4.17.6	Design Twitter	A k-way merge with an early stop at 10
4.17.7	Find Median from Data Stream ★	Two heaps facing each other

★ marks the Blind 75 subset.

When not to use a heap

When the values are bounded small integers — bucket or count instead, and get O(n). That is the linear solution to 4.4.5 and the follow-up to 4.17.7.

When you need the k-th element once, from an array you may reorder — quickselect is O(n) average.

When k is close to n — the heap's advantage disappears; just sort.

When you need to delete an arbitrary element — heaps cannot do it efficiently. Use lazy deletion with a "to remove" map, or a balanced tree.

What the interviewer will push on

"Min-heap or max-heap?" The root is the item you evict. Say it that way.

"Why not sort?" Sorting is O(n \log n) and needs the whole collection; a size-k heap is O(n \log k) and works on a stream.

"Can you beat O(n \log k)?" Quickselect for a one-off selection, O(n) average.

"Why is heapify O(n)?" Most nodes are near the bottom and barely sift.

"What if the data does not fit in memory?" The size-k heap holds only k items. For approximate percentiles at scale, name t-digest or Count-Min sketch.

One thing to volunteer: say the discard rule out loud — "anything outside the top k now can never re-enter it" — before writing the loop. That sentence is what justifies throwing data away, and it is the whole design.

Recall

• A heap gives the extreme in O(1) and inserts or removes in O(\log n). It does not sort.
• The root is the item you evict. k largest → min-heap; k smallest → max-heap.
• Three shapes: size-k heap (top k, streams), k-way merge (one candidate per source), two heaps (the middle of a stream).
• Python's heapq is min-only — negate for a max-heap, on the way in and out. heapify is O(n). Push tuples with a tiebreaker.
• Quickselect beats a heap for a one-off k-th element: O(n) average, because it recurses into one side and the sizes halve.
• Bounded small values beat a heap entirely — count into buckets for O(n).
• Heaps cannot delete an arbitrary element; use lazy deletion or a balanced tree.

Next: 4.17.1 Kth Largest Element in a Stream — the size-k heap in its simplest form.