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.

Practice

1. What is the main purpose of using two heaps (a max-heap and a min-heap) when finding the median of a data stream?

easy

A. To sort all numbers in ascending order

B. To efficiently keep track of the lower half and upper half of the numbers separately

C. To store all numbers in a single data structure

D. To find the maximum number in the data stream

Solution

1. Step 1: Understand the role of two heaps

   The max-heap stores the smaller half of the numbers, and the min-heap stores the larger half.

2. Step 2: Explain how this helps find the median

   By balancing these heaps, the median is either the top of one heap or the average of the tops of both heaps.

3. Final Answer:

   To efficiently keep track of the lower half and upper half of the numbers separately -> Option B

4. Quick Check:

   Two heaps split data halves = A [OK]

Hint: Two heaps split data halves for median [OK]

Common Mistakes:

• Thinking heaps sort all numbers fully
• Using only one heap for median
• Confusing max-heap and min-heap roles

2. Which of the following is the correct way to insert a number into the two heaps when maintaining the median in JavaScript?

easy

A. Always insert into min-heap

B. Always insert into max-heap

C. Insert into max-heap if number is less than or equal to max-heap root; else insert into min-heap

D. Insert randomly into either heap

Solution

1. Step 1: Decide heap based on number value

   If the number is smaller or equal to the max-heap root, it belongs to the lower half, so insert into max-heap.

2. Step 2: Otherwise insert into min-heap

   If the number is greater, it belongs to the upper half, so insert into min-heap.

3. Final Answer:

   Insert into max-heap if number is less than or equal to max-heap root; else insert into min-heap -> Option C

4. Quick Check:

   Compare with max-heap root to choose heap [OK]

Hint: Compare with max-heap root to choose heap [OK]

Common Mistakes:

• Inserting all numbers into one heap
• Not comparing with max-heap root
• Inserting randomly without condition

3. Consider the following JavaScript code snippet using two heaps to find the median after inserting numbers 5, 15, 1, 3:

const maxHeap = new MaxHeap();
const minHeap = new MinHeap();

function addNum(num) {
  if (maxHeap.size() === 0 || num <= maxHeap.peek()) {
    maxHeap.insert(num);
  } else {
    minHeap.insert(num);
  }

  if (maxHeap.size() > minHeap.size() + 1) {
    minHeap.insert(maxHeap.extract());
  } else if (minHeap.size() > maxHeap.size()) {
    maxHeap.insert(minHeap.extract());
  }
}

addNum(5);
addNum(15);
addNum(1);
addNum(3);

const median = maxHeap.size() > minHeap.size() ? maxHeap.peek() : (maxHeap.peek() + minHeap.peek()) / 2;
console.log(median);

What is the output printed?

medium

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 into maxHeap (empty). Insert 15 into minHeap (15 > 5). Insert 1 into maxHeap (1 <= 5). Insert 3 into maxHeap (3 <= 5). Now maxHeap has 3 elements, minHeap has 1.

2. Step 2: Balance heaps sizes

   maxHeap size (3) > minHeap size (1) + 1, so move maxHeap.extract() (which is 5) to minHeap. Now maxHeap has [3,1], minHeap has [5,15]. Median is average of maxHeap.peek()=3 and minHeap.peek()=5, so (3+5)/2 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Median after balancing = 4 [OK]

Hint: Balance heaps sizes, median is middle or average [OK]

Common Mistakes:

• Not balancing heaps after insertion
• Taking median as maxHeap.peek() only
• Incorrect heap extraction order

4. The following code snippet is intended to maintain the median using two heaps, but it has a bug:

function addNum(num) {
  if (num < maxHeap.peek()) {
    maxHeap.insert(num);
  } else {
    minHeap.insert(num);
  }

  if (maxHeap.size() > minHeap.size() + 1) {
    minHeap.insert(maxHeap.extract());
  } else if (minHeap.size() > maxHeap.size()) {
    maxHeap.insert(minHeap.extract());
  }
}

What is the bug in this code?

medium

A. It inserts all numbers into minHeap

B. It uses > instead of >= in the size comparison

C. It balances heaps incorrectly by moving elements the wrong way

D. It does not handle the case when maxHeap is empty before peek()

Solution

1. Step 1: Identify peek() usage problem

   The code calls maxHeap.peek() without checking if maxHeap is empty, causing an error on first insertion.

2. Step 2: Explain impact of missing empty check

   Without checking, calling peek() on empty maxHeap throws an error, so the first number cannot be inserted properly.

3. Final Answer:

   It does not handle the case when maxHeap is empty before peek() -> Option D

4. Quick Check:

   Empty maxHeap peek() causes error [OK]

Hint: Check heap empty before peek() to avoid errors [OK]

Common Mistakes:

• Ignoring empty heap before peek()
• Assuming heaps always balanced before insert
• Incorrect size comparison operators

5. You are given a stream of numbers: [2, 4, 7, 1, 5, 3]. Using two heaps (max-heap for lower half, min-heap for upper half), what is the median after inserting all numbers? Also, explain why balancing the heaps is important in this process.

hard

A. 3.5; Balancing keeps heaps sizes equal or off by one to find median correctly

B. 4; Balancing is not necessary if we always insert correctly

C. 3; Balancing helps to sort the entire stream

D. 5; Balancing is used to find max value quickly

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 2 (maxHeap empty, goes to maxHeap). Insert 4 (4 > 2, minHeap). Insert 7 (7 > 2, minHeap). Now minHeap has 2 elements, maxHeap 1, so move minHeap.extract() (4) to maxHeap. Insert 1 (1 <= 4, maxHeap). Insert 5 (5 > 4, minHeap). Insert 3 (3 <= 4, maxHeap). Heaps are balanced with maxHeap size 4 and minHeap size 2, move maxHeap.extract() (4) to minHeap to balance sizes.

2. Step 2: Calculate median and explain balancing

   Now maxHeap has [3,2,1] with peek()=3, minHeap has [4,5,7] with peek()=4. Since sizes equal (3 and 3), median is (3 + 4)/2 = 3.5. Balancing keeps heaps sizes equal or off by one to find median correctly from the tops.

3. Final Answer:

   3.5; Balancing keeps heaps sizes equal or off by one to find median correctly -> Option A

4. Quick Check:

   Balanced heaps give median 3.5 [OK]

Hint: Balance heaps sizes to get median from tops [OK]

Common Mistakes:

• Not balancing heaps after each insertion
• Calculating median from unsorted data
• Confusing median with max or min values