Two heaps facing each other

Split the data at the middle and keep both halves' inner edges available. That is the median, maintained.

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.

1import heapq2 3lower = []                   # max-heap of the smaller half, negated4upper = []                   # min-heap of the larger half5 6for value in [5, 2, 8]:7    heapq.heappush(lower, -value)8    heapq.heappush(upper, -heapq.heappop(lower))   # hand the largest over9    if len(upper) > len(lower):10        heapq.heappush(lower, -heapq.heappop(upper))11    print(sorted(-x for x in lower), sorted(upper))

Everything on the left is at or below everything on the right, and the left never trails the right in size.

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 it· 8 min

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 [].

added	lower	upper	median
5
15
1

Problem· 30 min

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.

1import heapq2 3lower = [] # max-heap of the smaller half, negated4upper = [] # min-heap of the larger half5 6for value in [5, 2, 8]:7 heapq.heappush(lower, -value)8 heapq.heappush(upper, -heapq.heappop(lower)) # hand the largest over9 if len(upper) > len(lower):10 heapq.heappush(lower, -heapq.heappop(upper))11 print(sorted(-x for x in lower), sorted(upper))

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.

added

lower

upper

median