Numbers arrive one at a time and after each one I want the running median. How would you keep it?

Two heaps that partition the stream

Keep every value seen so far split into two halves. The lower half lives in a max-heap, so its largest element is at the top. The upper half lives in a min-heap, so its smallest element is at the top. Two invariants hold after every insertion.

The first is the value partition: every element of the low heap is less than or equal to every element of the high heap. The second is the size balance: the two heaps differ in size by at most one. Given both, the median is immediate. If the sizes are unequal, it is the top of the larger heap. If they are equal, it is the average of the two tops.

Write both invariants down before writing code. Almost every wrong implementation of this problem is wrong because it maintains one of them and assumes the other follows.

The push-then-transfer discipline

The reliable insertion procedure does not decide which heap the value belongs in. It pushes unconditionally into one heap, immediately moves that heap's top into the other, and then corrects the sizes.

Concretely: push the new value into the low heap, then pop the low heap's top and push it into the high heap. That two-step guarantees the value partition regardless of where the new value fell, because whatever ends up as the low heap's maximum has been compared against everything in the low heap by the heap itself. Then, if the high heap has become larger than the low heap, move its top back. Every step is a heap operation, so the whole insertion is O of log n, and none of it requires you to reason about where the value sits relative to the existing median.

PriorityQueue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder());  // lower half
PriorityQueue<Integer> high = new PriorityQueue<>();                          // upper half

void add(int value) {
    low.add(value);
    high.add(low.poll());              // route through low so the partition cannot break
    if (high.size() > low.size()) {
        low.add(high.poll());          // surplus element, by convention, lives in low
    }
}

double median() {
    if (low.size() > high.size()) return low.peek();
    return (low.peek() + (long) high.peek()) / 2.0;   // widen before adding
}

The convention that the surplus element lives in the low heap is arbitrary but it must be fixed, because median() reads it. Choosing the convention in add and forgetting it in median gives you an implementation that is correct on even counts and off by one element on odd ones.

Balancing by size alone puts a large value in the wrong half

Here is the version that looks equivalent and is not. Suppose you insert by pushing into whichever heap is currently smaller, on the reasoning that this keeps the sizes balanced by construction.

Take the stream 1, 2, 3. The correct procedure leaves the low heap holding 1 and 2, with 2 on top, and the high heap holding 3; sizes two and one, and the median reads off the larger heap as 2. Now 0 arrives. The high heap is the smaller one, so the size-only rule pushes 0 into it, and the high heap's top becomes 0. The value partition is now violated: 0 sits in the upper half while 1 and 2 sit in the lower. Sizes are two and two, so median() averages the two tops, 2 and 0, and reports 1. The true median of 0, 1, 2, 3 is 1.5.

The size balance held perfectly and the answer was still wrong, which is the point. Size balance is what makes the median readable off the tops; the value partition is what makes the tops mean anything. An implementation that maintains only the cheaper invariant produces answers that are plausible, wrong, and never throw.

Costs, and why not just keep a sorted list

Insertion is O of log n and reading the median is O of 1, with O of n space for the values retained. Compare that to the two alternatives a candidate should be able to dismiss briskly. Re-sorting after every arrival is O of n log n per element. Keeping a sorted array and inserting in place has an O of log n search but an O of n shift, so it is linear per element, and it wins only for small n where the shift is a single memory move and the heap's pointer chasing is not.

The other thing worth saying is what the heaps cannot do. A binary heap supports look at the top, remove the top, and insert. It does not support finding or removing an arbitrary element in better than linear time, and it does not support asking for the element at rank k for any k other than the extremes.

That limitation is exactly what the sliding-window variant runs into. If the median is wanted over the last k values only, elements must leave the structure in arrival order rather than in value order, and neither heap can find the departing element. The usual repairs are lazy deletion, where you mark the value as expired and discard it when it surfaces at a top while tracking the effective sizes separately, or replacing the heaps with a structure that supports order-statistic queries and arbitrary removal, such as a balanced tree keyed by value with counts. Reaching straight for lazy deletion and being explicit that the sizes must then be tracked independently of the heap sizes is a strong signal, because it shows you know which operation the data structure is missing rather than only that the problem is harder.