AntInLoop

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.