Heaps and Priority Queues
Two heaps facing each other
Split the data at the middle and keep both halves' inner edges available. That is the median, maintained.
Key idea
Why one heap cannot do it
A heap gives you an extreme. The median is not an extreme; it is the middle, which a single heap has no way to reach.
Back in U4 this exact limitation appeared: the augmented-stack lesson noted that a median cannot be extended from the answer for a smaller collection, unlike a minimum or a sum. The fix is not a cleverer heap, it is two of them.
Why it works
The arrangement
Keep a max-heap of the lower half and a min-heap of the upper half. Every value in the lower half is at or below every value in the upper half.
The two tops are then the two innermost values, sitting either side of the middle. If the halves are equal in size, the median is the average of the tops. If one is larger by one, its top is the median.
Keep the size difference at no more than one, and always in the same direction, so reading the answer needs no case analysis beyond even or odd.
Watch the two halves fill. Only the insertion is shown; reading the answer off the two tops is the part to work out yourself.
Tip
The push-pop-push dance
The insertion looks roundabout and it is doing something specific. Pushing into the lower half and then handing its largest to the upper half guarantees the new value lands in the correct half no matter what it was, without any comparison against the current median.
Then the rebalance moves one back if the upper half has grown too large. Three heap operations, no branches on value, and the ordering invariant holds by construction rather than by case analysis.
The alternative is to compare the incoming value against a top and push into the right side directly, which is fewer operations and more branches. Both are fine; the branchless version is easier to defend as correct.
Gotcha
Negate consistently and only at the boundary
The lower half stores negated values, so its true top is -lower[0]. Every read and every write across that boundary needs the sign flip, and missing one produces a median that is wrong only sometimes.
Keeping the negation confined to push and pop, and never letting a negated value be compared against a real one, is what makes this survivable. Writing a tiny helper for each side is worth the extra lines if it stops the confusion.
Cost
Cost
Adding is a fixed number of heap operations, so O(log n). Reading the median is O(1), which is the requirement that forces this design in the first place.
Compare with keeping a sorted list: reading the median would be O(1) but inserting would be O(n) because of the shifting. And compare with sorting on demand, which is O(n log n) per query. The two-heap arrangement is the only one that makes both operations cheap.
Where else this shows up
Any time a problem wants a running statistic from the middle of a stream, this is the shape. Percentiles other than the median work the same way with an uneven split.
It also answers the sliding-window median, with the added difficulty of removing values that have expired, which heaps do not support directly. That variation needs lazy deletion, and knowing that the plain two-heap arrangement does not cover it is worth as much as knowing the arrangement.
Trace the two heaps
Add 5, then 15, then 1 to an empty structure. After each add, give the contents of the lower half as actual values in descending order, the upper half in ascending order, and the median. Write an empty half as [].
This activity type is not wired up yet.
Find Median From Data Stream
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.