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.

Pick a sub-pattern above. Each is independently linkable — start where the problem statement points.

↑ choose one

— / 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