Free Heaps lessonsHeaps · Stage 2 · Merging streams · Step 4

The middle value so far

Report the median of a stream after each new number, by keeping the smaller half in a max-heap and the larger half in a min-heap. About 22 minutes.

Two halves

The median is the middle of the sorted numbers. Instead of sorting, keep two groups: the smaller half and the larger half. Every number in the small group is no bigger than every number in the large group.

The small group lives in a max-heap, so its biggest number is on top. The large group lives in a min-heap, so its smallest is on top. The median is made from these two tops.

Low half: max-heap; its top is the biggest of the small.

High half: min-heap; its top is the smallest of the large.

In code

if len(low) == len(high):
    median = (-low[0] + high[0]) / 2
else:
    median = -low[0]

Medians after each of 4, 9, 1, 6. The answers shown are twice the median.

Only 4. The median is 4, twice that is 8.

Move 1 of 4

Add, pass across, rebalance

To add a number, put it into the low half. Then move the biggest of the low half across to the high half. This guarantees that every low number is at most every high number.

Then rebalance: the low half may hold at most one more number than the high half. If the high half became bigger, move its smallest back. If the counts are equal, the median is the average of the two tops; otherwise it is the top of the low half.

Sizes: low has the same count as high, or one more.

Equal sizes: median is the average of the two tops.

In code

if len(high) > len(low):
    top = heapq.heappop(high)
    heapq.heappush(low, -top)

Quick check

The low half has 3 numbers and the high half has 3 numbers. What is the median?

AThe average of the top of the low half and the top of the high half
BThe top of the low half
CThe top of the high half

Show the answer

The average of the top of the low half and the top of the high half. With an even count, the median is the average of the two middle numbers.

Your problem

Running median, doubled

Numbers arrive one at a time in the array nums. After each arrival, find the median of all numbers so far: the middle number if the count is odd, or the average of the two middle numbers if it is even. Because the average can end in .5, return twice the median each time, so the answers are whole numbers. Return the list with one entry per arrival.

Example

nums = [5, 2, 8, 1] → [10, 7, 10, 7]

0 ≤ length of nums ≤ 3,000 · -10,000 ≤ nums[i] ≤ 10,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.