Use a heap when the problem repeatedly asks for the smallest, largest, or next most important item while the set keeps changing.
Heap Pattern Map
| Need | Heap Type | Practice |
|---|---|---|
| Kth largest | Min-heap of size k | Kth Largest |
| Top k frequent | Frequency min-heap | Top K Frequent |
| Merge sorted lists | Min-heap of current heads | Merge K Lists |
| Streaming median | Max-heap + min-heap | Median Finder |
Rule Of Thumb
If you only need k results, avoid storing and sorting everything unless the constraints are tiny.
FAQs
When is a heap better than sorting?
When you need only a small top-k result or the data arrives over time.
Why use two heaps for median?
The lower half and upper half need different priority orders, so one heap is not enough.