Heap & Priority Queue

01 / The shared mechanism

A heap gives you cheap access to the extreme — the min or the max — while everything else stays in a loose, half-sorted shape. Three sub-patterns: one heap for top-k, two heaps for the running median, and a min-heap of source pointers for merging k sorted streams.

01 / The one-sentence essence

To track the k most extreme elements out of N, keep a heap of size k whose root is the worst of the k — every new element either kicks the root out or doesn't.

Problemtop k largest from a streamStream[3, 1, 5, 12, 2, 11, 7, 8]k3

stream

123

115

— heap is empty —

heap = [ ]

Keep a min-heap of size k = 3. The root is the smallest of the top-k — any new element strictly larger kicks the root out.

step

0 / 17

heap size

min (root)

—

action

init

0 / 17

streamk (max 7)

02 / The pattern signature

# top-k largest — min-heap of size kheap ← [ ]for x in stream:if |heap| < k:heap.push(x)elif x > heap[0]:heap.replace_root(x)return sort(heap, descending)# top-k smallest: max-heap and the dual comparison

03 / When to recognize this pattern

"top k / kth"

You need the k most or least extreme — not the full sorted order. The whole point is to spend less than O(N log N).

"streaming / online"

Elements arrive one at a time and you can't see them all at once. A heap of size k gives a constant-memory answer no matter how long the stream is.

"frequency / weighted"

The "extreme" relation isn't on the raw value — it's on a derived key like a count or a distance. Same algorithm, different comparator.

"running quantile / percentile"

The kth-largest of a window or stream is exactly what a size-k heap maintains for free. For the running median, two heaps are required — see two-heaps.

04 / Common pitfalls

Using a max-heap to find the largest.

For top-k largest you want a min-heap of size k — the root is the smallest of the keepers, and incoming larger elements kick it out. A max-heap of size k would put the biggest seen so far on top and never let you cheaply check the kth element.

ii.

Strict > vs non-strict ≥ when replacing.

With strict >, an incoming element equal to the root is rejected — the existing duplicate stays. With ≥, it gets cycled in. The two produce the same set on inputs without duplicates; on duplicates, they differ. Match your problem.

iii.

Reaching for a heap when sort is fine.

If you already have all N elements in memory and k is close to N, sorting is simpler and competitive. The heap wins when N ≫ k or the data is streaming and you can't buffer all of it.

05 / Go practice — on LeetCode

Four problems. The first is the canonical kth-largest. The second adds a frequency key — same algorithm, different comparator. The third stresses the streaming setup. The fourth is a classic application that pairs heaps with greedy selection.

01Kth Largest Element in an Array— LC 215medium→02Top K Frequent Elements— LC 347medium→03Kth Largest Element in a Stream— LC 703easy→04K Closest Points to Origin— LC 973medium→

— / When to use which

top-k

Use when you need the k most extreme values — not the full sorted order.

stream · O(N log k) · LC 215 / 347 / 703

two heaps

Use when you need the running median — split the data into a low half (max-heap) and a high half (min-heap).

median · max-heap + min-heap · LC 295

k-way merge

Use when you have k sorted streams and need the next-smallest across all of them.

merge · (val, src, idx) · LC 23 / 378