Synthesis: which pattern to use?
Three heap patterns covered. The section is short, but the reflex it trains is powerful: recognizing when the question is about repeated extremes and reaching for the heap.
The section's decision tree
Does the problem ask for the SMALLEST or LARGEST repeatedly, without needing everything sorted?
→ think HEAP. From there:
1. "The K largest / smallest / K-th / K most frequent"?
→ HEAP OF SIZE K (K largest → min-heap; K smallest → max-heap)
2. "Merge / pick the next smallest among SEVERAL sorted sources"?
→ K-WAY MERGE (min-heap with the head of each source)
3. "Median of a stream / balance two halves"?
→ TWO HEAPS (max-heap of the smaller half + min-heap of the larger one)
And the general reflex: heap = "what is the extreme right now?" in O(log n). If you catch yourself wanting to re-sort at every step, or to compare repeatedly to find the minimum/maximum of a changing set, that is a sign for a heap.
The section's full map
| Pattern | Key question | Structure | Time |
|---|---|---|---|
| Top-K | "the K largest/smallest" | heap of size K | O(n log k) |
| k-way merge | "next smallest among K sources" | min-heap of K heads | O(N log k) |
| Two heaps | "median of a stream" | max-heap + min-heap | O(log n)/insertion |
The idea that ties it all together: the heap keeps the extreme accessible in O(1) and readjusts in O(log n) when the set changes. That is why it is the "priority" tool — and it reappears as a priority queue in Dijkstra (graphs) and in schedulers.
Section quiz
Statements you have not seen in the lessons. Identify the pattern and the why. 6+ correct: ready for the exam.
🧠 Section quiz: Heap
0/61. 'Return the K closest points to the origin.' Which pattern and which heap?
2. 'Connect all sticks with minimum cost (joining a and b costs a+b).' Which pattern?
3. 'A stream of numbers; at any moment, return the current median.' Which pattern?
4. 'Merge K sorted arrays into one.' Why does the heap beat concatenate+sort?
5. For the K LARGEST elements, which kind of heap of size K and why?
6. What is the core idea that defines when to use a heap?
Ready for the exam?
The Heap section's final exam has three brand-new problems — easy, medium, and hard — with hidden cases. The hard one (k-th smallest in a sorted matrix) is a disguised k-way merge: start from the corner and expand neighbors with a min-heap. The three lessons cover everything you need.
Good luck on the exam! Go back to the section page and click "Final exam".