Two Heaps

Two heaps maintain an ordered partition as values arrive. A max-heap named lower stores the lower half. A min-heap named upper stores the upper half. Their roots expose the two values beside the partition, which makes the current median available without sorting the accumulated stream.

Two invariants make the result correct:

1. Every value in lower is less than or equal to every value in upper.
2. lower.Count equals upper.Count or exceeds it by one.

A value no greater than lower.Peek() enters lower. Anything larger enters upper. If the size rule breaks, moving one boundary root restores it. An odd number of values leaves the median at lower.Peek(). With an even count, the two roots are averaged.

VisualizationVisualizationComplexityComplexity

Visualization

The stream rail shows insertion order. After each value arrives, the lower max-heap exposes the largest value from the lower half and the upper min-heap exposes the smallest value from the upper half. Rebalancing moves only a root, preserving both the partition and the size difference of at most one.

Complexity

TimeSpace

• Insert and rebalance: O(log n)
• Read median: O(1)
• Process n running medians: O(n log n)

n

number of values processed so far

Where the Pattern Applies

The pattern fits running medians and other streaming problems that need both sides of an ordered boundary. It differs from Top-K Elements: Top-K discards values outside its k survivors, while Two Heaps retains everything because either half may affect a later median.

Arbitrary deletion changes the mechanism. A sliding-window median must remove expired values, but the basic heap API has to scan its backing collection to locate one. Indexed heaps or lazy-deletion maps can add that removal path. They are extra machinery and only earn their place when values actually expire.

C# running median with PriorityQueue

public sealed class RunningMedian
{
    private readonly PriorityQueue<int, long> lower = new(); // max-heap via negative priority
    private readonly PriorityQueue<int, int> upper = new();  // min-heap
 
    public void Add(int value)
    {
        if (lower.Count == 0 || value <= lower.Peek())
            lower.Enqueue(value, -(long)value);
        else
            upper.Enqueue(value, value);
 
        if (lower.Count > upper.Count + 1)
        {
            int moved = lower.Dequeue();
            upper.Enqueue(moved, moved);
        }
        else if (upper.Count > lower.Count)
        {
            int moved = upper.Dequeue();
            lower.Enqueue(moved, -(long)moved);
        }
    }
 
    public double Median() => lower.Count switch
    {
        0 => throw new InvalidOperationException("No values have been added."),
        _ when lower.Count > upper.Count => lower.Peek(),
        _ => ((long)lower.Peek() + upper.Peek()) / 2.0
    };
}

.NET’s queue is a min-heap, so a long negative priority reverses only the lower heap. Widening before negation handles int.MinValue, and widening before the even-count sum prevents overflow.

References

• PriorityQueue<TElement, TPriority>