Sorting & SearchingIntermediate
Two Heaps
Use a max-heap and a min-heap together to efficiently track the median or partition elements into two balanced groups.
Initialize Two Heaps
Max-heap stores lower half, min-heap stores upper half
Max-Heap (Lower Half)
Empty
Min-Heap (Upper Half)
Empty
Step 1/6
Speed:
When to Use
- Find median of a data stream
- Balance elements into two halves
- Sliding window median
- Scheduling with two competing priorities
Key Indicators
- Running median / streaming median
- Two balanced groups
- Maximize smallest or minimize largest
- Dual priority queues
Complexity
Time
O(log n) per insert
Space
O(n)
Common Problems
Find Median from Data StreamSliding Window MedianIPOLast Stone WeightMaximize Capital
Code
max_heap = [] # lower half (negate values)
min_heap = [] # upper half
def add(num):
heappush(max_heap, -num)
heappush(min_heap, -heappop(max_heap))
if len(min_heap) > len(max_heap):
heappush(max_heap, -heappop(min_heap))
def median():
if len(max_heap) > len(min_heap):
return -max_heap[0]
return (-max_heap[0] + min_heap[0]) / 2Want all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)