AI Hints
Home›DSA in Python Tutorial›Designing Data Structures
DSA in Python · Lesson 114 of 132

Practice: Median of a Stream

Two heaps.

⏱ 2 min read▶ Video at 2:16:01🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Numbers arrive one at a time, and after each one, you need the median, the middle value. Sorting every time is far too slow. The clever answer uses two heaps.

Practice: Median of a Stream
From the video: Practice: Median of a Stream
  • Numbers keep arriving
  • Find the median each time
  • Two heaps

Two halves

Keep the smaller half of the numbers in a max heap, and the larger half in a min heap. Keep the halves balanced, so they differ in size by at most one. Then the median is right at the top of the heaps. Either the top of the bigger one, or the average of both tops.

Low halfa max heap
High halfa min heap
Balancedsizes differ by at most 1
Medianat the tops

Median finder

Python only has min heaps, so we store the low half as negative numbers. Each new number goes into the low half, then its largest moves to the high half. If the high half gets bigger, we move one back. Run it. The median after each number.

median.pypython
import heapq

low, high = [], []

def add(x):
    heapq.heappush(low, -x)
    heapq.heappush(high, -heapq.heappop(low))
    if len(high) > len(low):
        heapq.heappush(low, -heapq.heappop(high))

def median():
    if len(low) > len(high):
        return -low[0]
    return (-low[0] + high[0]) / 2

for x in [5, 15, 1, 3, 8]:
    add(x)
    print(x, "->", median())
Output
5 -> 5
15 -> 10.0
1 -> 5
3 -> 4.0
8 -> 5

Summary

Keep the low half in a max heap and the high half in a min heap. The median sits at the tops, and each new number costs O of log N. Next, the biggest number in every window.

Key takeaways
  • Max heap for the low half
  • Min heap for the high half
  • Median at the tops
Next up: Practice: Sliding Window Maximum — a deque of candidates