Heap / Priority Queue
Maintain quick access to the min or max element for top-k, merge, and scheduling problems.
- • Top K elements
- • Merging K sorted lists
- • Running median
- • Task scheduling by priority
- • Need sorted iteration of all elements
- • Need random access by index
- • Using max heap when you need min heap (or vice versa)
- • Not understanding heap size constraints for top-k
Key Invariant
A heap gives O(log n) insert and O(1) peek — use it when you repeatedly need the extreme element