Heaps problems, grouped by pattern
A heap gives you the smallest or largest item in O(log n) while items keep arriving. It is the standard answer to top-k, kth largest and merging k sorted sources.
When to reach for it
- Top k, kth largest or kth smallest
- Merge k sorted lists or arrays
- Repeatedly take the best remaining option
Mistakes to watch for
- Using a max heap when a size-k min heap is enough
- Comparator overflow with a - b in Java
- Not re-adding the next item from the same source
The 6 problems
1Top K / Kth Largest / Smallest
- Kth Largest Element in an Array Animated Medium
- Kth Largest Element in a Stream Animated Easy
2Composite comparator
- Top K Frequent Elements Animated Medium
3Merge K Sorted
- Merge k Sorted Lists Animated Hard
- Merge k Sorted Arrays Animated Medium
4Advanced
- Find K Pairs with Smallest Sums Animated Medium