Course contentsShow
← Computer Science
Lesson 615 of 2,87214. Heaps and Priority QueuesFree lesson

Median Maintenance with Two Heaps

Maintain running median of a stream using a max-heap for lower half and min-heap for upper half.

Median Maintenance with Two Heaps

You'll learn how to efficiently track the median of a data stream by using two heaps working in tandem.

The Core Challenge

Imagine you're receiving numbers one at a time and need to instantly report the median after each arrival. The naïve approach—sorting the entire list each time—takes O(n log n) per number. We can do much better with a clever two-heap structure.

The Two-Heap Strategy

Split your numbers into two balanced halves:

  • Max-heap holds the smaller half of numbers (largest value at the top)
  • Min-heap holds the larger half of numbers (smallest value at the top)

Think of it like two mountains facing each other: the max-heap's peak points upward showing the largest small number, while the min-heap's peak points upward showing the smallest large number. The median lives right between these two peaks!

How It Works

  1. Insert new numbers: Add to one heap based on comparison with current median
  2. Rebalance: Keep heaps equal in size (or differ by 1) by moving the top element from one heap to the other
  3. Find median:
    • If heaps are equal size, median is the average of both tops
    • Otherwise, median is the top of the larger heap

Each insertion takes O(log n) time, and finding the median is instant O(1).

Example Walk-Through

Stream: [5, 15, 1, 3]

  • Add 5: max-heap=[5], min-heap=[], median=5
  • Add 15: max-heap=[5], min-heap=[15], median=10
  • Add 1: max-heap=[5,1], min-heap=[15], rebalance → max-heap=[1], min-heap=[5,15], median=5
  • Add 3: max-heap=[3,1], min-heap=[5,15], median=4

Key Takeaway: Maintaining a running median efficiently requires splitting data into two balanced heaps—a max-heap for the lower half and a min-heap for the upper half—giving O(log n) insertions and O(1) median queries.