Maintain a streaming median with two heaps

Clarify the observable contract

Maintain the exact median of all integers received so far. The lower half is a max-heap and the upper half a min-heap. Their sizes differ by at most one, with the lower half owning the extra element. For an even count return the average of the two boundary values as decimal, and reject querying an empty stream.

The two invariants are ordering and balance: every lower-half value is no greater than every upper-half value, and low.Count equals high.Count or exceeds it by one. The median is then determined by their boundary roots. Choosing the lower heap to own the extra value simplifies odd-length queries.

Walk through the verified program

The first two maximum integers produce the same maximum median. Adding the minimum integer leaves the lower boundary at maximum because two of three values are maximum. Adding zero gives the sorted middle values zero and maximum, whose average is 1073741823.5. Converting before addition avoids overflowing the integer sum.

Insertion first chooses a side by comparison with low.Peek, then moves at most one root to repair size imbalance. Moving the maximum lower value upward or minimum upper value downward preserves ordering. The fourth output is a useful arithmetic boundary because one middle value is maximum and the other zero.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

var medians = new Median();
foreach(int x in new[] { int.MaxValue, int.MaxValue, int.MinValue, 0 }) { medians.Add(x); Console.WriteLine(medians.Value().ToString("0.0",CultureInfo.InvariantCulture)); }
sealed class Median {
    private readonly PriorityQueue<int,int> low = new(Comparer<int>.Create((a,b)=>b.CompareTo(a)));
    private readonly PriorityQueue<int,int> high = new();
    public void Add(int x) { if(low.Count==0 || x<=low.Peek()) low.Enqueue(x,x); else high.Enqueue(x,x);
        if(low.Count>high.Count+1) { int v=low.Dequeue(); high.Enqueue(v,v); }
        if(high.Count>low.Count) { int v=high.Dequeue(); low.Enqueue(v,v); } }
    public decimal Value() { if(low.Count==0) throw new InvalidOperationException("empty"); return low.Count==high.Count ? ((long)low.Peek()+high.Peek())/2m : low.Peek(); }
}

Account for time, storage and allocations

Each insertion performs a bounded number of heap operations, costing O(log n) time; reading the median is O(1). Both heaps together retain all n input values, so this exact unbounded-history structure uses O(n) storage. A streaming interface is not automatically constant-memory.

PriorityQueue is a min-heap abstraction, so the lower heap uses a reversed comparer rather than negated priorities. Retaining duplicate values is necessary because median depends on multiplicity. The two heaps do not deduplicate observations, and their O(n) storage grows even when every incoming value is identical.

Review assumptions and likely defects

Negating an integer priority to simulate a max-heap fails at int.MinValue. The comparer reverses CompareTo instead, avoiding subtraction and negation overflow. Sliding-window medians require removing expired values or another data structure; this implementation handles append-only history only.

Compute an even median after widening the sum, not after overflowing an int expression. decimal division by two represents the integer and half-integer results exactly for these inputs. A result printed with one decimal place is formatting, not an approximation algorithm or a floating-point benchmark.

Practice one: discriminate edge cases

Test duplicates, a single minimum integer, an even pair spanning both integer extremes and querying before the first insertion. Hint: check size and ordering invariants after every insertion, not just the final printed median.

For each prefix, build an independently sorted array and compare its median with the heap result. Keep the extreme pair and duplicate-heavy cases in that oracle. This tests both internal balance and externally visible values, while avoiding a second implementation that merely copies the same heap operations.

Practice two: defend an extension

Design a bounded-memory service for approximate percentiles rather than an exact all-history median. Specify error tolerance, mergeability and window semantics. Explain what you would stop promising when replacing the exact two-heap state with a summary.

An approximate quantile summary needs a stated error model, such as rank error, and a clear time window. If the requirement is an exact sliding median, expiration changes the problem and requires indexed removal or delayed-deletion bookkeeping. Neither requirement can be satisfied simply by capping one of these heaps and discarding arbitrary values.

Evaluate correctness and interview reasoning

The interview proof should connect the two invariants to the returned median before listing complexity. Then trace an insertion that crosses heaps and an even-count average at the numeric extremes. A senior answer notices that exact all-history statistics retain unbounded history and asks whether approximation or windowing is acceptable. The fixture uses the real framework priority queue and a safe comparison primitive, so no custom heap mechanics are being hidden. Independent prefix-oracle checks are particularly valuable because a final median can look correct even after an earlier balancing error. An empty-state query must be tested before any insertion because Peek has no valid root then; the method deliberately throws a named InvalidOperationException rather than inventing a median of zero.