Heaps efficiently find min/max elements. Essential for Top-K, merge K sorted lists, and scheduling problems.
Time
Insert: O(log n), Extract Min/Max: O(log n), Peek: O(1)
Space
O(n)
Problems
4 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Kth Largest Element in an Array | Medium | Google Meta Amazon |
| 2 | Merge K Sorted Lists | Hard | Google Amazon Microsoft |
| 3 | Find Median from Data Stream | Hard | Google Amazon Microsoft |
| 4 | Top K Frequent Elements | Medium | Amazon Google Meta |
Min-heap: parent ≤ children. Max-heap: parent ≥ children
In Python: heapq (min-heap by default). For max-heap, negate values
Two heaps pattern: max-heap for lower half, min-heap for upper half → O(1) median
Heap is NOT a sorted structure — only the root is guaranteed min/max
