Finding Median in a Data Stream (Two Heaps)

Introduction: The “Middle Man” Problem

Finding the median of a sorted array is easy ($O(1)$). But what if the data is a stream?

• Sort Every Time: $O(N \log N)$ per new item. Too slow.
• Maintain Sorted Array: $O(N)$ to shift elements per insertion. Still too slow for millions of points.

The Two Heaps pattern allows you to find the median in $O(1)$ time and add new elements in $O(\log N)$ time. It’s the gold standard for real-time statistical monitoring.

What Problem does it solve?

• Input: A continuous stream of numbers.
• Output: The current median at any moment.
• The Promise: Balanced performance between insertion and query.

Core Idea (Intuition)

Divide the data into two halves:

1. Lower Half: Store the smaller half of the data in a Max-Heap. The largest of the small numbers is at the top.
2. Upper Half: Store the larger half of the data in a Min-Heap. The smallest of the large numbers is at the top.

The Median is always either the top of one of these heaps (if total items are odd) or the average of the two tops (if total items are even).

How it Works

1. Balance: Keep the sizes of the two heaps nearly equal (difference $\le 1$).
2. Insert:
   • Add the new number to the appropriate heap.
   • If the heaps become unbalanced, “move” the top element from the larger heap to the smaller one.
3. Find Median:
   • If total items are odd, return the top of the larger heap.
   • If even, return (MaxHeap.top + MinHeap.top) / 2.

Typical Business Scenarios

• ✅ Performance Analysis: Calculating the “Median Response Time” of a web service as requests flow in.
• ✅ Financial Tech: Real-time median price calculation for assets in a volatile market.
• ✅ Interactive Data Apps: Dashboards that update stats as the user uploads data.

Performance & Complexity

• Add Item: $O(\log N)$.
• Find Median: $O(1)$.
• Space: $O(N)$ to store all items.

Summary

"The Two Heaps pattern is like a balanced scale. By splitting the data into two opposing heaps, it keeps the 'Middle Man' (the median) right at the top where you can see it instantly."