Two Heaps Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide
Split items into a "small half" (max-heap) and a "large half" (min-heap). The tops give you the median instantly.
3 sub-patterns · 6 questions
What is this pattern?
One heap gives you the smallest item or the largest, but never the middle. Two heaps can. Split the items into two halves:
low, a max-heap holding the smaller half. Its top is the biggest of the small numbers.high, a min-heap holding the larger half. Its top is the smallest of the big numbers.
Keep two rules true after every insert: every item in low ≤ every item in high, and the sizes differ by at most one (say low may have one extra). Then the two tops sit right at the middle. The median is low.top() when the count is odd, and the average of the two tops when it is even. Each insert is O(log N) and each median is O(1).
The same "two heaps facing each other" idea also solves two-pools problems. One heap holds what you can use now (free servers, affordable projects). The other holds what becomes usable later (busy servers by finish time, projects by required capital). Items move from the second heap to the first as time passes or money grows.
A line of people sorted by height, split down the middle into two rooms. In the "short" room you only watch the tallest person; in the "tall" room only the shortest. Those two people stand right at the middle of the whole line. When someone new arrives, they go into one room, and if the rooms get uneven, the person at the door walks across.
See it move
Heaps shown in pop order, top on the left. low holds the smaller half (top = its largest); high holds the larger half (top = its smallest). The two tops sit at the middle.
stream = [5,15,1,3,8,7,9]step 1/18- low size
- 0
- high size
- 1
- moved to high
- 5
5 goes into low, but it is the biggest there, so it moves straight to high. Now every number in low is still ≤ every number in high.
`P2(c3,+5)` = project 2 needs capital 3 and earns 5. Locked projects are sorted by capital (blue = moved to available, purple = done). The available heap is shown in pop order, highest profit on the left.
profits = [3,2,5,1,4], capital = [0,1,3,2,6], w = 0, k = 3step 1/7- capital
- 0
- projects left
- 3
Projects sorted by required capital form the locked pool. P0 needs 0, so it unlocks first. Start with capital 0, at most 3 projects.
How do I recognise it?
"Median" of numbers that keep arriving (a stream).
"Median of every window" of size k.
You need the boundary between two halves: the largest of the small part and the smallest of the large part.
Two pools: items that are available now vs items that unlock later (servers busy until time t, projects that need more capital).
Pick the cheapest from either end: the first c and the last c candidates, each in its own heap.
Looks like Two Heaps, but isn't
If all the numbers are known up front and you need the median once, sort it (O(N log N)) or quickselect it (average O(N)). Two heaps are for when numbers keep arriving and the median is asked again and again.
If K is fixed, one heap of size K is enough. Two heaps are for a moving rank like the median, which is position N/2 and shifts as N grows.
The arrays are sorted and fixed, so binary search for the cut in O(log(min(m, n))). No heaps needed.
For the max or min of a window, a deque does it in O(N). Two heaps are only needed when you want the middle of the window.
How would I discover it from scratch?
Don't memorise “use two heaps”. Ask these questions in order — the pattern falls out.
After every new number, sort everything seen so far and read the middle: O(N log N) per query. Keeping a sorted array and inserting in place is O(N) per insert: better, but still slow.
Sub-patterns
Same core idea, different rule for “valid”. Learn them in this order.
Running median
2 questionsNumbers only arrive. Keep low (max-heap) and high (min-heap) balanced; the median is read from the tops.
Sliding median
1 questionsRunning median plus removals: as the window slides, one number enters and one leaves.
Two pools (available / locked)
3 questionsOne heap holds what can be used now, ordered by quality; the other holds what unlocks later, ordered by unlock time or cost. Move items across as the condition changes.
Don't mix these up
Top K wants a fixed rank (the Kth), so one heap of size K is enough. The median is a moving rank (N/2) that shifts as N grows, so you need both halves.
Each heap shows the item nearest the middle: the largest of the small half and the smallest of the large half. Swap them and the tops are the far ends: the overall min and max.
Both give O(log k) per slide. Multisets can erase any value directly and are simpler to get right in C++. Lazy deletion is the way when only a heap is available (Java, Python), and it teaches why stale items are harmless until they reach a top.
Code templates (C++)
Running median
Push into low, move its top to high, and move one back if high is bigger. Average the tops as double: (low.top() + (double)high.top()) / 2, or two big ints overflow.
// 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
}
};Sliding median (lazy deletion)
A leaving number is only recorded in delayed, and the balance counter treats it as gone. After each change, rebalance, then prune any top that is in delayed. Sizes must count only live numbers.
// Sliding window median with two heaps and lazy deletion.
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
priority_queue<int> low; // smaller half
priority_queue<int, vector<int>, greater<int>> high; // larger half
unordered_map<int, int> delayed; // value -> copies waiting to be removed
int lowSize = 0, highSize = 0; // LIVE counts only
auto prune = [&](auto& h) { // drop stale tops
while (!h.empty() && delayed.count(h.top())) {
if (--delayed[h.top()] == 0) delayed.erase(h.top());
h.pop();
}
};
auto rebalance = [&]() { // low has the same size or one more
if (lowSize > highSize + 1) {
high.push(low.top()); low.pop(); lowSize--; highSize++; prune(low);
} else if (lowSize < highSize) {
low.push(high.top()); high.pop(); highSize--; lowSize++; prune(high);
}
};
vector<double> res;
for (int i = 0; i < (int)nums.size(); i++) {
int x = nums[i];
if (low.empty() || x <= low.top()) { low.push(x); lowSize++; }
else { high.push(x); highSize++; }
if (i >= k) { // nums[i-k] leaves the window
int gone = nums[i - k];
delayed[gone]++;
if (gone <= low.top()) { lowSize--; if (gone == low.top()) prune(low); }
else { highSize--; if (gone == high.top()) prune(high); }
}
rebalance();
if (i >= k - 1)
res.push_back(k % 2 ? (double)low.top() : ((double)low.top() + high.top()) / 2.0);
}
return res;
}Two pools: available and locked
locked is ordered by when an item unlocks; available by how good it is. Before each pick, move every unlocked item across. If nothing is available, either stop (IPO) or jump time to the next unlock (servers).
// IPO: locked projects sorted by capital; available profits in a max-heap.
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
int n = profits.size();
vector<pair<int, int>> locked; // (capital needed, profit)
for (int i = 0; i < n; i++) locked.push_back({capital[i], profits[i]});
sort(locked.begin(), locked.end()); // unlock order
priority_queue<int> available; // profits we can afford now
int p = 0;
while (k--) {
while (p < n && locked[p].first <= w) // move EVERY unlocked project across
available.push(locked[p++].second);
if (available.empty()) break; // nothing affordable: stop
w += available.top(); available.pop(); // best affordable project
}
return w;
}