A binary heap gives O(log n) insert/extract-min(or max) — ideal for "top K", "kth largest", "merge sorted streams", and "running median" problems. The two-heap trick — a max-heap for the lower half plus a min-heap for the upper half — gives O(log n) median maintenance.
Sub-patterns
- A — Top-K. Maintain a heap of size k for the k largest/smallest/closest.
- B — K-Way Merge. Merge several sorted sources using a heap of their current fronts.
- C — Two-Heap Median. A max-heap and a min-heap split the data in half for O(log n) median updates.
- D — Heap-Driven Greedy Scheduling. Always process the currently-best-available choice.
Practice set (12)
- Easy — Kth Largest Element in a Stream, Last Stone Weight
- Medium — Kth Largest Element in an Array, Top K Frequent Elements, Task Scheduler, K Closest Points to Origin, Reorganize String, Meeting Rooms II (Premium, also relevant to Intervals)
- Hard — Merge k Sorted Lists, Find Median from Data Stream, IPO, Trapping Rain Water II
Pending
Top-K
Maintain a heap of size k to track the k largest, smallest, or closest elements.
Pending
K-Way Merge
Merge several sorted sources at once using a heap of their current fronts.
Pending
Two-Heap Median
A max-heap for the lower half plus a min-heap for the upper half, giving O(log n) running-median updates.
Pending
Heap-Driven Greedy Scheduling
Always process the currently-best-available choice, popped off a heap.
Notes from readers
Comments — via GitHub