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

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 growing list of numbers, like daily temperatures or scores, but you get the numbers one by one and want to know the middle value at any time.

Doing this by sorting the whole list every time a new number arrives is like rearranging your entire bookshelf every time you get a new book--slow and tiring!

The Problem

Sorting the entire list after each new number is slow because it takes more time as the list grows.

Also, manually finding the middle value each time is error-prone and wastes a lot of effort.

The Solution

Using two heaps (special boxes that keep numbers in order) lets you quickly find the middle value without sorting everything again.

One heap keeps the smaller half of numbers, the other keeps the bigger half, so the middle is always easy to find.

Before vs After

✗ Before

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

✓ After

const maxHeap = new MaxHeap();
const minHeap = new MinHeap();
addNumber(newNumber);
const median = getMedian();

What It Enables

This method lets you find the middle value instantly as new numbers come in, even if the list grows very large.

Real Life Example

Streaming apps use this to show the median rating of a movie as viewers keep rating it live, without waiting for all ratings to finish.

Key Takeaways

Manually sorting each time is slow and inefficient.

Two heaps keep track of smaller and larger halves separately.

Median can be found quickly without full sorting.

Practice

1. What is the main purpose of using two heaps (a max heap and a min heap) in the Median of Data Stream problem?

easy

A. To sort all numbers in ascending order

B. To store all numbers in a single data structure

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

D. To remove duplicates from 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 tops of both heaps.

3. Final Answer:

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

4. Quick Check:

   Two heaps split data halves = efficient median [OK]

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

Common Mistakes:

• Thinking heaps sort all numbers fully
• Using one heap only
• Confusing heaps with arrays

2. Which TypeScript syntax correctly declares a max heap using a priority queue for numbers?

easy

A. const maxHeap = new PriorityQueue<number>((a, b) => b - a);

B. const maxHeap = new PriorityQueue<number>((a, b) => a - b);

C. const maxHeap = new PriorityQueue<number>();

D. const maxHeap = new PriorityQueue<number>((a, b) => a + b);

Solution

1. Step 1: Understand max heap comparator

   Max heap comparator returns positive if first is less than second, so b - a creates max heap.

2. Step 2: Check each option

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); uses (b - a) which is correct for max heap; others do not create max heap order.

3. Final Answer:

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); -> Option A

4. Quick Check:

   Comparator b - a = max heap [OK]

Hint: Max heap comparator subtracts first from second [OK]

Common Mistakes:

• Using a - b for max heap (creates min heap)
• Not providing comparator
• Using addition in comparator

3. Given the following sequence of numbers inserted into the data stream: [5, 15, 1, 3], what is the median after all insertions using two heaps?

medium

A. 3

B. 4

C. 5

D. 8

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 -> maxHeap=[5] (top=5), minHeap=[]; Insert 15 -> minHeap=[15] (top=15), sizes 1:1; Insert 1 -> maxHeap=[5,1] (top=5), sizes 2:1; Insert 3 -> maxHeap=[5,3,1] (top=5), sizes 3:1 -> balance (max.size > min.size+1), move max.top=5 to minHeap -> maxHeap=[3,1] (top=3), minHeap=[5,15] (top=5), sizes 2:2.

2. Step 2: Calculate median from heaps

   Sizes equal, median = (maxHeap.top + minHeap.top)/2 = (3 + 5)/2 = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Median of [5,15,1,3] = 4 [OK]

Hint: Median is average of two heap tops if sizes equal [OK]

Common Mistakes:

• Taking median as top of one heap only
• Not balancing heaps after insertion
• Wrong average calculation

4. Consider this TypeScript snippet for adding a number to the data stream median finder:

if (num <= maxHeap.peek()) {
  maxHeap.enqueue(num);
} else {
  minHeap.enqueue(num);
}

// Balance heaps
if (maxHeap.size() > minHeap.size() + 1) {
  minHeap.enqueue(maxHeap.dequeue());
} else if (minHeap.size() > maxHeap.size()) {
  maxHeap.enqueue(minHeap.dequeue());
}

What is the bug in this code?

medium

A. It compares num with minHeap.peek() instead of maxHeap.peek()

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

C. It uses enqueue instead of push for heaps

D. It does not handle empty maxHeap before peek() call

Solution

1. Step 1: Analyze peek() usage on maxHeap

   If maxHeap is empty, calling peek() causes error because no element exists yet.

2. Step 2: Identify missing empty check

   Code should check if maxHeap is empty before peek() or handle initial insertion separately.

3. Final Answer:

   It does not handle empty maxHeap before peek() call -> Option D

4. Quick Check:

   Empty heap peek() causes runtime error [OK]

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

Common Mistakes:

• Assuming heaps always have elements
• Mixing enqueue and push methods
• Balancing heaps incorrectly

5. You want to extend the Median of Data Stream solution to support removing numbers from the stream efficiently. Which data structure modification is best to support both insertion and removal while maintaining median calculation?

hard

A. Use two heaps with a hash map to mark removed elements lazily

B. Use two balanced binary search trees (like AVL or Red-Black trees) instead of heaps

C. Use a single sorted array and binary search for insertion and removal

D. Use two queues to store lower and upper halves

Solution

1. Step 1: Understand removal challenge in heaps

   Heaps do not support efficient arbitrary removal, so direct removal is costly.

2. Step 2: Explain lazy removal with hash map

   Mark elements as removed in a hash map and skip them during heap operations to simulate removal efficiently.

3. Step 3: Compare other options

   Balanced trees support removal but are more complex; arrays are inefficient; queues do not maintain order.

4. Final Answer:

   Use two heaps with a hash map to mark removed elements lazily -> Option A

5. Quick Check:

   Lazy removal with hash map + heaps = efficient median update [OK]

Hint: Lazy removal with hash map keeps heaps efficient [OK]

Common Mistakes:

• Trying direct removal from heaps
• Using arrays causing slow operations
• Ignoring complexity of balanced trees