Two heaps

Question 1

What is the Two Heaps pattern and when is it used?

Answer 1

Uses min/max heaps to track median or balanced sets.

Use Case: Dynamic median, scheduling.

Example: [Find Median from Data Stream]. Action: Verbalize use case aloud.

Question 2

What are the key steps in the Two Heaps pattern?

Answer 2

1. Maintain small (max heap) and large (min heap).
2. Balance heaps (size diff ≤ 1).
3. Compute median from heap tops.

Action: Explain steps for [Find Median from Data Stream] aloud.

Question 3

How does the Two Heaps pattern apply to [Find Median from Data Stream]?

Answer 3

Find median of streaming numbers. Use max heap for lower half, min heap for upper.

Action: Verbalize solution logic aloud.

Question 4

What are the complexity and gotchas of the Two Heaps pattern?

Answer 4

Time: O(log n) insert, O(1) median, Space: O(n).
Gotchas: Empty stream, equal numbers.

Action: List edge cases for [Find Median from Data Stream] aloud.

Question 5

Code example of the Two Heaps pattern.

Answer 5

```python
from typing import List
from heapq import heappush, heappop
class MedianFinder:
def __init__(self) -> None:
self.small: List[int] = [] # max heap
self.large: List[int] = [] # min heap
def add_num(self, num: int) -> None:
heappush(self.small, -num)
heappush(self.large, -heappop(self.small))
if len(self.large) > len(self.small):
heappush(self.small, -heappop(self.large))
def find_median(self) -> float:
if len(self.small) > len(self.large):
return float(-self.small[0])
return (-self.small[0] + self.large[0]) / 2
~~~