Why Median of Data Stream Using Two Heaps in DSA Javascript?

The Big Idea

What if you could instantly know the middle value of a never-ending list without sorting it every time?

The Scenario

Imagine you are tracking the middle value of a list of numbers that keeps growing, like monitoring the median price of houses sold every day.

Every time a new house price comes in, you want to quickly know the median without sorting the entire list again.

The Problem

Manually sorting the list every time a new number arrives is slow and frustrating.

It wastes time and can cause mistakes if the list is very long or updates happen often.

The Solution

Using two heaps (one max heap and one min heap) lets you keep track of the lower half and upper half of the numbers separately.

This way, you can quickly find the median by looking at the tops of the heaps without sorting the whole list every time.

Before vs After

✗ Before

let numbers = [];
numbers.push(newNumber);
numbers.sort((a, b) => a - b);
let median = numbers.length % 2 === 0 ? (numbers[numbers.length/2 - 1] + numbers[numbers.length/2]) / 2 : numbers[Math.floor(numbers.length/2)];

✓ After

let maxHeap = new MaxHeap();
let minHeap = new MinHeap();
// Add number to one of the heaps and balance
// Median is top of maxHeap or average of tops

What It Enables

You can efficiently find the median in a stream of numbers in real-time, even as new data keeps coming.

Real Life Example

Streaming live stock prices and instantly knowing the median price helps traders make quick decisions without delays.

Key Takeaways

Manually sorting every time is slow and inefficient.

Two heaps split data into lower and upper halves for quick median access.

This method works well for continuous data streams and real-time calculations.