01
Running median (Two Heaps Sub-pattern)
Numbers only arrive. Keep low (max-heap) and high (min-heap) balanced; the median is read from the tops.
Signals in the problem statement
- ›
"median after each insertion"
- ›
"design a class with addNum and findMedian"
What makes it different
Median of a Stream prints the median after every number of a given array. Find Median from Data Stream is the same thing as a class. Both need the average as a double, computed without int overflow. LeetCode's follow-ups (all numbers in [0, 100]) swap the heaps for a counting array.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Median of a Stream of IntegersWalkthroughMediumBasic Anchor·GeeksforGeeks
- 2Find Median from Data StreamWalkthroughHardBasic Reinforcement·LeetCode #295
Template
running-median-template.cpp
// Running median: low = smaller half (max-heap), high = larger half (min-heap).
class MedianFinder {
priority_queue<int> low; // top = largest small number
priority_queue<int, vector<int>, greater<int>> high; // top = smallest large number
public:
void addNum(int x) {
low.push(x);
high.push(low.top()); low.pop(); // check the biggest small one against high
if (high.size() > low.size()) { low.push(high.top()); high.pop(); } // low keeps the extra
}
double findMedian() {
if (low.size() > high.size()) return low.top();
return (low.top() + (double)high.top()) / 2.0; // double: no int overflow
}
};Remember this · Two Heaps
Trigger
Running median, sliding median, choosing from two pools (available vs locked).
Think
Can I split the data into two halves and only care about the boundary between them?
Key question
How do I rebalance so the sizes differ by at most one?