Median of Data Stream Using Two Heaps in DSA Javascript - Deep Dive

Overview - Median of Data Stream Using Two Heaps

What is it?

Median of Data Stream Using Two Heaps is a method to find the middle value of numbers that keep coming in one by one. Instead of waiting for all numbers, it updates the middle value quickly as new numbers arrive. It uses two special lists called heaps to keep track of smaller and larger halves of the numbers. This way, it can tell the median fast at any time.

Why it matters

Without this method, finding the middle number in a growing list would be slow because you'd have to sort all numbers every time. This would make real-time tasks like monitoring sensor data or live scores inefficient. Using two heaps solves this by keeping the data organized so the median is always ready quickly, making systems faster and more responsive.

Where it fits

Before learning this, you should understand what a median is and basic data structures like arrays and heaps (priority queues). After this, you can explore other streaming algorithms or advanced data structures for real-time analytics and statistics.

Mental Model

Core Idea

Keep the smaller half of numbers in one heap and the larger half in another, so the median is always at the top of one or both heaps.

Think of it like...

Imagine you have two boxes: one holds all the smaller toys, and the other holds all the bigger toys. The median toy is the one right between these two boxes, easy to find because you only look at the top toy in each box.

┌───────────────┐       ┌───────────────┐
│ Max-Heap      │       │ Min-Heap      │
│ (Smaller half)│       │ (Larger half) │
│               │       │               │
│    5          │       │    8          │
│   / \         │       │   / \         │
│  3   4        │       │  9   10       │
└───────────────┘       └───────────────┘

Median is either top of Max-Heap or average of tops of both heaps.

Build-Up - 7 Steps

1

Foundation

Understanding Median Concept

Concept: Learn what median means and how to find it in a list of numbers.

Median is the middle number when all numbers are sorted. If the count is odd, it's the center number. If even, it's the average of the two center numbers. For example, in [3, 1, 4], sorted is [1, 3, 4], median is 3. In [1, 2, 3, 4], median is (2+3)/2 = 2.5.

Result

You can find the middle value of any fixed list by sorting and picking the center.

Understanding median is key because the whole method aims to find this middle value efficiently as numbers come in.

2

Foundation

Basics of Heaps (Priority Queues)

Concept: Learn what heaps are and how max-heaps and min-heaps work.

A heap is a special tree where the biggest (max-heap) or smallest (min-heap) element is always at the top. Max-heap keeps the largest number on top, min-heap keeps the smallest on top. This helps quickly find and remove these elements. For example, max-heap of [3, 1, 4] has 4 on top.

Result

You can quickly get the largest or smallest number from a heap without sorting the whole list.

Knowing heaps lets you organize numbers so you can find medians fast without sorting all numbers every time.

3

Intermediate

Splitting Data Stream into Two Heaps

🤔Before reading on: do you think both heaps should always have the same number of elements? Commit to your answer.

Concept: Divide incoming numbers into two heaps: max-heap for smaller half, min-heap for larger half.

When a new number arrives, compare it with the top of max-heap. If smaller or equal, add to max-heap; else add to min-heap. Then balance heaps so their sizes differ by at most one. This keeps smaller half in max-heap and larger half in min-heap.

Result

Numbers are split so max-heap holds smaller half, min-heap holds larger half, balanced in size.

Splitting and balancing heaps ensures the median is always near the top of one or both heaps, enabling quick median retrieval.

4

Intermediate

Calculating Median from Two Heaps

🤔Before reading on: if max-heap has one more element than min-heap, is median the top of max-heap or min-heap? Commit to your answer.

Concept: Median depends on heap sizes: if equal, average tops; if unequal, median is top of larger heap.

If both heaps have same size, median = (max-heap top + min-heap top) / 2. If one heap has one extra element, median = top of that heap. This works because heaps hold halves of sorted data.

Result

Median is quickly found by looking only at the tops of the two heaps.

Knowing how heap sizes affect median calculation lets you get the middle value instantly without full sorting.

5

Intermediate

Implementing Add Number Operation

🤔Before reading on: do you think adding a number always requires rebalancing heaps? Commit to your answer.

Concept: Add new number to correct heap and rebalance if needed to maintain size property.

Steps: 1) Add number to max-heap or min-heap based on comparison. 2) If size difference > 1, move top element from larger heap to smaller heap. This keeps heaps balanced and median calculation correct.

Result

After each addition, heaps remain balanced and median can be found immediately.

Rebalancing after each addition is crucial to maintain the structure that allows fast median retrieval.

6

Advanced

JavaScript Code for Median Finder Class

🤔Before reading on: do you think JavaScript has built-in heaps? Commit to your answer.

Concept: Implement the two heaps approach in JavaScript using custom heap classes and median finder methods.

JavaScript lacks built-in heaps, so we create MinHeap and MaxHeap classes with insert and extract methods. MedianFinder class uses these heaps to add numbers and find median. Code example: class MinHeap { constructor() { this.heap = []; } insert(val) { /* insert logic */ } extract() { /* extract min */ } peek() { return this.heap[0]; } size() { return this.heap.length; } } class MaxHeap { constructor() { this.heap = []; } insert(val) { /* insert logic */ } extract() { /* extract max */ } peek() { return this.heap[0]; } size() { return this.heap.length; } } class MedianFinder { constructor() { this.maxHeap = new MaxHeap(); this.minHeap = new MinHeap(); } addNum(num) { /* add and rebalance */ } findMedian() { /* return median */ } } This structure supports streaming data median calculation.

Result

You get a working JavaScript class that can add numbers and return median efficiently.

Building heaps from scratch in JavaScript deepens understanding of heap operations and how median streaming works.

7

Expert

Performance and Edge Cases in Streaming Median

🤔Before reading on: do you think this method handles duplicate numbers and negative values correctly? Commit to your answer.

Concept: Analyze time complexity, handle duplicates, negative numbers, and large data streams efficiently.

Each addNum operation takes O(log n) due to heap insertions and rebalancing. findMedian is O(1). Duplicates and negative numbers are handled naturally by heaps since they compare values. For very large streams, memory can grow, so sometimes approximate methods are used. Also, balancing ensures no heap grows too large compared to the other, preventing skewed data.

Result

The method is efficient and robust for real-world streaming data with various values.

Understanding performance and edge cases prepares you to use this method confidently in production and know its limits.

Under the Hood

Two heaps maintain two halves of the data stream: max-heap stores the smaller half with the largest element on top, min-heap stores the larger half with the smallest element on top. When a new number arrives, it is placed in one heap based on comparison with max-heap top. Then heaps are balanced to keep size difference ≤ 1. Median is either the top of the larger heap or average of both tops. This avoids sorting all data repeatedly.

Why designed this way?

Sorting every time a new number arrives is too slow (O(n log n)). Using two heaps reduces insertion to O(log n) and median retrieval to O(1). The design balances simplicity and efficiency, leveraging heap properties to maintain order without full sorting. Alternatives like balanced binary search trees exist but are more complex to implement and maintain.

Incoming Number
     │
     ▼
Compare with Max-Heap Top
     │
 ┌───────────────┐
 │               │
 │  Max-Heap     │◄───────────────┐
 │ (Smaller half)│                │
 └───────────────┘                │
     │                           │
     ▼                           │
Insert into Max-Heap or Min-Heap │
     │                           │
     ▼                           │
 ┌───────────────┐        ┌───────────────┐
 │               │        │               │
 │  Min-Heap     │───────►│ Balance Sizes │
 │ (Larger half) │        │ (Size diff ≤1)│
 └───────────────┘        └───────────────┘
                             │
                             ▼
                      Median Calculation
                             │
                             ▼
                  Median = Top(s) of Heap(s)

Myth Busters - 4 Common Misconceptions

Quick: Do you think the median is always the top of the max-heap? Commit to yes or no.

Common Belief: The median is always the top element of the max-heap.

Reality: The median depends on heap sizes: if heaps are equal size, median is average of tops of both heaps; if not, median is top of the larger heap.

Why it matters: Assuming median is always max-heap top leads to wrong median values when heaps are balanced, causing incorrect results in applications.

Quick: Do you think heaps must always have the same number of elements? Commit to yes or no.

Common Belief: Both heaps must always have the exact same number of elements.

Reality: Heaps can differ in size by at most one element to correctly represent median for odd number of total elements.

Why it matters: Forcing equal sizes can cause unnecessary moves and incorrect median calculation for odd-sized data streams.

Quick: Do you think this method requires sorting the entire data stream each time? Commit to yes or no.

Common Belief: You must sort all numbers every time a new number arrives to find the median.

Reality: The two heaps method avoids full sorting by maintaining partial order in heaps, making median retrieval efficient.

Why it matters: Believing sorting is needed leads to inefficient implementations that can't handle large or fast data streams.

Quick: Do you think duplicates or negative numbers break the two heaps method? Commit to yes or no.

Common Belief: Duplicates or negative numbers cause errors or incorrect medians in the two heaps method.

Reality: Heaps handle duplicates and negative numbers naturally because they compare values without restrictions.

Why it matters: Misunderstanding this limits the method's use and causes unnecessary complexity to handle these cases.

Expert Zone

1

Balancing heaps after every insertion is critical; even a single imbalance can cause median miscalculation.

2

Choosing max-heap for smaller half and min-heap for larger half simplifies median calculation but reversing roles is possible with adjusted logic.

3

In languages without built-in heaps, implementing efficient heap operations is key to performance; naive arrays cause slowdowns.

When NOT to use

Avoid this method when data stream is extremely large and memory is limited; approximate algorithms like Count-Min Sketch or reservoir sampling may be better. Also, if data is mostly static or batch, sorting once is simpler. For multidimensional medians or weighted medians, specialized algorithms are needed.

Production Patterns

Used in real-time analytics dashboards, financial tickers, sensor data monitoring, and anywhere median of live data is needed. Often combined with sliding window techniques to find median over recent data only. Implementations optimize heap operations and memory usage for high throughput.

Connections

Balanced Binary Search Trees

Alternative data structure for maintaining sorted data dynamically.

Understanding balanced trees helps appreciate tradeoffs in insertion and median retrieval times compared to heaps.

Streaming Algorithms

Builds on streaming data processing principles for real-time computation.

Knowing streaming algorithms shows how median finding fits into broader real-time data analysis challenges.

Real-Time Traffic Control Systems

Application domain where median of data streams is critical for decision making.

Recognizing this connection highlights the practical importance of efficient median calculation in safety-critical systems.

Common Pitfalls

#1 Not rebalancing heaps after adding a number.

Wrong approach:

addNum(num) {
if (num <= this.maxHeap.peek()) {
this.maxHeap.insert(num);
} else {
this.minHeap.insert(num);
}
// Missing rebalance step
}

Correct approach:

addNum(num) {
if (this.maxHeap.size() === 0 || num <= this.maxHeap.peek()) {
this.maxHeap.insert(num);
} else {
this.minHeap.insert(num);
}
if (this.maxHeap.size() > this.minHeap.size() + 1) {
this.minHeap.insert(this.maxHeap.extract());
} else if (this.minHeap.size() > this.maxHeap.size() + 1) {
this.maxHeap.insert(this.minHeap.extract());
}
}

Root cause:

Forgetting that heaps must be balanced to keep median calculation correct.

#2 Assuming median is always max-heap top regardless of heap sizes.

Wrong approach:

findMedian() {
return this.maxHeap.peek(); // always
}

Correct approach:

findMedian() {
if (this.maxHeap.size() === this.minHeap.size()) {
return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
} else if (this.maxHeap.size() > this.minHeap.size()) {
return this.maxHeap.peek();
} else {
return this.minHeap.peek();
}
}

Root cause:

Misunderstanding how heap sizes affect median calculation.

#3 Using arrays and sorting on every insertion instead of heaps.

Wrong approach:

addNum(num) {
this.nums.push(num);
this.nums.sort((a,b) => a-b);
}
findMedian() {
const mid = Math.floor(this.nums.length / 2);
if (this.nums.length % 2 === 0) {
return (this.nums[mid - 1] + this.nums[mid]) / 2;
} else {
return this.nums[mid];
}
}

Correct approach:

Use two heaps as described to avoid sorting on every insertion.

Root cause:

Not knowing efficient data structures for dynamic median calculation.

Key Takeaways

Median of a data stream can be found efficiently by splitting numbers into two heaps representing smaller and larger halves.

Max-heap stores the smaller half with the largest element on top; min-heap stores the larger half with the smallest element on top.

Balancing the heaps so their sizes differ by at most one ensures the median is always at the top of one or both heaps.

Adding a number involves inserting into the correct heap and rebalancing, making median retrieval O(1) and insertion O(log n).

This method is practical for real-time systems and large data streams where sorting every time is too slow.