Two Heaps & the Running Median

August 2026 · 20 min read

A single heap privileges one end. If you need the middle — the median — you need two, arranged back to back. This technique is the answer to Find Median from Data Stream, and it generalises to any problem where you must maintain a balanced split of a growing multiset.

Two Heaps, Facing Each Other

Split the elements into a lower half and an upper half:

• lo — a max-heap holding the smaller half. Its root is the largest of the small values.
• hi — a min-heap holding the larger half. Its root is the smallest of the large values.

        lo (max-heap)              hi (min-heap)
      [1, 3, 5, 8]                 [9, 11, 14, 20]
              ^                     ^
              |                     |
          lo.top() = 8          hi.top() = 9
                  \             /
                   the median lives here

The two roots are the two elements straddling the middle. With an even total the median is their average; with an odd total it is the root of whichever heap was allowed to grow larger. Both are O(1) reads.

Insertion: Push, Shuttle, Rebalance

The clean formulation always routes the new element through both heaps, which makes the ordering invariant automatic and removes all the comparison branching people usually write:

#include <queue>
#include <vector>
#include <functional>

class MedianFinder {
    std::priority_queue<int> lo;                                             // max-heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> hi;        // min-heap

public:
    void addNum(int num) {
        lo.push(num);                    // always enters the lower half first
        hi.push(lo.top());               // its largest migrates to the upper half
        lo.pop();

        if (hi.size() > lo.size()) {     // keep lo >= hi in size
            lo.push(hi.top());
            hi.pop();
        }
    }

    double findMedian() const {
        if (lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};

Why the shuttle works: pushing into lo then immediately moving lo.top() to hi guarantees that whatever ends up in hi is at least as large as everything remaining in lo — regardless of where the new value belonged. You never compare against hi.top() at all. The cost is one extra pair of heap operations, bought in exchange for eliminating a class of edge-case bugs.

Then the single rebalance restores invariant (2). Because we always push to lo and move exactly one element across, hi can only ever exceed lo by one, so one corrective move is always enough.

A Trace

add 5    lo:[5]        hi:[]         median 5
add 2    lo:[2]        hi:[5]        median 3.5
add 8    lo:[5,2]      hi:[8]        median 5
add 1    lo:[2,1]      hi:[5,8]      median 3.5
add 9    lo:[5,2,1]    hi:[8,9]      median 5

Walk the third step to see the shuttle in action. Before it, lo = [2], hi = [5]. Push 8 into lo, so lo = [8,2] and its root is 8. Move that root to hi, giving lo = [2], hi = [5,8]. Now hi is bigger, so pull its root back: lo = [5,2], hi = [8]. Sizes are 2 and 1, the ordering holds, and the median is lo.top() = 5.

Complexity

Compare with the alternatives: keeping a sorted vector gives O(1) median but O(n) insertion from the shift; sorting on every query is O(n log n) per call. An order-statistic tree matches the two-heap bounds and also supports arbitrary rank queries, but it is far more code and slower in practice for the median-only case.

Sliding Window Median

The hard extension: maintain the median over a window of size k, which requires removing the element leaving the window. Heaps have no efficient arbitrary erase — the problem Part 12 exists to solve.

Two workable approaches:

Lazy deletion. Keep a hash map of values pending removal. When a root is scheduled for deletion, pop it and decrement the count instead of returning it. Sizes must then be tracked separately from heap.size(), because the heaps contain ghosts:

std::unordered_map<int, int> pending;      // value -> how many copies to discard

auto prune = [&](auto& heap) {
    while (!heap.empty()) {
        auto it = pending.find(heap.top());
        if (it == pending.end() || it->second == 0) break;
        if (--it->second == 0) pending.erase(it);
        heap.pop();
    }
};

Prune only at the roots, only when you need to read them. Ghosts buried in the interior are harmless — they will surface eventually, and pruning them early would cost a scan.

Two multisets. Replace the heaps with std::multiset, using rbegin() of the lower set and begin() of the upper. Erasure by iterator is then O(log k) and exact. Slower by a constant factor than heaps, but dramatically simpler to get right — usually the better trade in an interview.

The Pattern Beyond Medians

Two heaps facing each other maintain any partition of a multiset into a bottom-p and top-q by rank. Adjust the balance invariant and you get:

• Arbitrary percentiles. Hold lo at ceil(p * n) elements instead of n/2, and lo.top() is the p-th percentile. Useful for streaming p99 latency without storing samples in sorted order.
• IPO / Maximum Capital. A min-heap on capital requirement feeds a max-heap on profit as projects become affordable — the same two-sided arrangement, gated by a different key on each side.
• Constrained scheduling. One heap of available items and one of pending items, with elements migrating as a clock advances. Part 10 builds on exactly this.

Practice

• Find Median from Data Stream hard — the canonical two-heap problem.
• Sliding Window Median hard — adds deletion; try both lazy deletion and multisets.
• IPO / Maximum Capital hard — two heaps keyed on different fields.
• Finding MK Average hard — three containers, same partitioning idea.
• Constrained Subsequence Sum hard — a heap maintaining a windowed maximum with lazy deletion.