Two Heaps: Running Median
Two Heaps & K-Way Merge: lesson 1 of 4
Two heaps face each other, and the middle sits between their roots.
Lesson 1 of 4 · 6 min
Two Heaps: Running Median
Step 1 of 16
Two heaps, back to back. The low half keeps its largest on top; the high half keeps its smallest. The middle lives between them.
The Idea
Keep the small half in a max-heap and the large half in a min-heap. The two roots sit either side of the middle, so the median is always one glance away — never a re-sort.
Every arrival enters the low side, then low's largest is handed across to high. One size check keeps the halves level.
Real-World Example
A spice market's double-pan balance. Each new weight lands on the left pan, the heaviest item there is passed to the right, and a pan that gets two ahead sends one back. Whatever rests nearest the pivot is the middle weight.
The Code
import heapq
def medians(stream):
low, high = [], [] # low: max-heap (negated)
out = []
for x in stream:
heapq.heappush(low, -x) # everything enters low
heapq.heappush(high, -heapq.heappop(low)) # hand low's largest across
if len(high) > len(low): # keep low the bigger half
heapq.heappush(low, -heapq.heappop(high))
out.append(-low[0] if len(low) > len(high)
else (-low[0] + high[0]) / 2)
return out
print(medians([5, 15, 1, 3])) # [5, 10.0, 5, 4.0]Your turn
What does this print?
import heapq
low, high = [-3, -1], [5, 9] # low is negated: it holds 3 and 1
heapq.heappush(low, -7)
heapq.heappush(high, -heapq.heappop(low))
print(-low[0], high[0])Mini quiz
1 / 3