Two Heaps

The Two Heaps pattern maintains an ordered partition while values arrive. A max-heap named lower stores the lower half, and a min-heap named upper stores the upper half. Their roots meet at the partition boundary, so the median is 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 new value enters lower when it is no greater than the lower root; otherwise it enters upper. Moving one root across restores the size rule. With an odd count, lower.Peek() is the median. With an even count, the median is the average of both roots.

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

n

number of values processed so far

TimeSpace

Insert and rebalance

• Time

Read median

• Time

Process n running medians

• Time

Where the Pattern Applies

The pattern fits running medians and other streaming partition problems where both sides of a boundary must remain available. It differs from Top-K Elements: Top-K keeps only k survivors and discards the rest, while Two Heaps retains every value because either half may contribute a future median.

Deletion changes the mechanism. Removing an arbitrary expired value, as in a sliding-window median, is not efficient with only the basic heap API because locating that value is linear. Indexed heaps or lazy-deletion maps add the missing removal path; they are justified only when the window actually expires values.

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.

Questions

Why is the lower half a max-heap and the upper half a min-heap?

The two roots must expose the values closest to the partition: the largest lower value and the smallest upper value. Those are exactly the one or two values needed for the median.

Why does rebalancing one root preserve the partition invariant?

If one heap is too large, its root is the boundary value on that side. Moving the largest lower value upward or the smallest upper value downward cannot place any other retained value across the boundary incorrectly.

References

• PriorityQueue<TElement, TPriority> — official .NET contract: an array-backed quaternary min-heap whose smallest priority is dequeued first.
• Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms — primary textbook treatment of heap invariants and logarithmic insertion/removal used by both halves.