Heap / Priority Queue
Overview
A heap is the right data structure whenever you need:
- Top-K anything, maintain a size-K heap. The heap gives O(n log K) instead of O(n log n) sorting.
- Streaming order statistics, kth smallest/largest, running median, sliding-window extremes.
- Scheduling with dynamic priorities, reorganize, task scheduling, meeting rooms.
- Greedy selection, always take the best (cheapest, earliest, largest) element, then update.
Python: heapq is a min-heap on a list. Negate values for max-heap. Heaps don’t support efficient arbitrary key lookup, pair with a hash map for “delete or update by key” (see Twitter).
Problems
- 703. Kth Largest Element in a Stream (Easy)
- 1046. Last Stone Weight (Easy)
- 973. K Closest Points to Origin (Medium)
- 215. Kth Largest Element in an Array (Medium)
- 621. Task Scheduler (Medium)
- 355. Design Twitter (Medium)
- 295. Find Median from Data Stream (Hard)
Key patterns unlocked here
- Size-K min-heap for online top-K, 703.
- Greedy selection with max-heap, 1046.
- Size-K heap by distance, 973.
- Quickselect vs. heap, 215 (classic time vs. space trade-off).
- Greedy scheduling with a counter and a max-heap, 621.
- Heap merge across per-user feeds, 355.
- Two heaps balancing a median, 295 (canonical).