Find median from a data stream

Track the median of a growing stream with two heaps: a max-heap for the lower half, a min-heap for the upper half, kept balanced.

The idea

Split the stream into two heaps: a max-heap holding the smaller half of the numbers, and a min-heap holding the larger half. After every insert, rebalance so the two halves differ in size by at most one. The median is then either the top of the larger heap, or the average of both tops when the halves are equal in size.

Code

public class MedianFinder {
    private PriorityQueue<int, int> lower = new(Comparer<int>.Create((a, b) => b - a)); // max-heap, smaller half
    private PriorityQueue<int, int> upper = new(); // min-heap, larger half

    public void AddNum(int num) {
        if (lower.Count == 0 || num <= lower.Peek()) lower.Enqueue(num, num);
        else upper.Enqueue(num, num);
        if (lower.Count > upper.Count + 1) { int m = lower.Dequeue(); upper.Enqueue(m, m); }
        else if (upper.Count > lower.Count) { int m = upper.Dequeue(); lower.Enqueue(m, m); }
    }

    public double FindMedian() =>
        lower.Count == upper.Count ? (lower.Peek() + upper.Peek()) / 2.0 : lower.Peek();
}

Tips

• Decide which heap a new number belongs to by comparing it with the current top of the lower (max-)heap, not by comparing it with every element.
• Rebalancing moves at most one element between heaps per insertion — it never needs to touch anything deeper.

In the .NET library

Each insert costs O(log n) for the heap push plus a possible O(log n) rebalance, but reading the median back is O(1) — a good trade when the median is read far more often than numbers are inserted.