Two Heaps Pattern (Running Median & Balancing)
The Two Heaps pattern partitions a dynamic dataset into a lower max-heap and upper min-heap of equal size to track running medians, sliding-window medians, and capital maximization in O(log n).
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Two Heaps Pattern (Running Median & Balancing)
The Two Heaps pattern splits a stream of numbers into two halves:
lo(Max-Heap): stores the smaller half (its top is the largest element of the lower half).hi(Min-Heap): stores the larger half (its top is the smallest element of the upper half).
Keeping lo.size() == hi.size() or lo.size() == hi.size() + 1 gives $O(1)$ median queries and $O(\log n)$ insertions—and also powers IPO (Maximize Capital) and Sliding Window Median!
Practice Problems
Hard
1. Maximize Capital / IPO (LeetCode 502)
You start with capital w and can complete at most k distinct projects (capital[i], profit[i]). Maximize your final capital.
Approach: Put all projects in a min-heap by required capital (or sort by capital) and push all currently affordable projects into a max-heap by profit. Repeat k times: unlock affordable projects, pop the highest profit! Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
int findMaximizedCapital(int k, int w, const std::vector<int>& profits, const std::vector<int>& capital) {
int n = static_cast<int>(profits.size());
std::vector<std::pair<int, int>> proj(n);
for (int i = 0; i < n; ++i) proj[i] = {capital[i], profits[i]};
std::sort(proj.begin(), proj.end());
std::priority_queue<int> maxProfit;
int i = 0;
while (k--) {
while (i < n && proj[i].first <= w) maxProfit.push(proj[i++].second);
if (maxProfit.empty()) break;
w += maxProfit.top();
maxProfit.pop();
}
return w;
}
int main() {
std::cout << findMaximizedCapital(2, 0, {1, 2, 3}, {0, 1, 1}) << "\n"; // 4
return 0;
}
</details>
---
Related Structures & Algorithms
- Binary Heap — includes the Running Median Two-Heap implementation.