Median of Data Stream Using Two Heaps in DSA Typescript - Execution Trace

Concept Flow - Median of Data Stream Using Two Heaps

New number arrives

↓

Compare with max-heap root

↓

Add to max-heap

↓

Balance heaps if size diff > 1

↓

Calculate median

↓

Output median

Each new number is added to one of two heaps (max-heap for lower half, min-heap for upper half). Heaps are balanced to keep sizes close. Median is derived from heap roots.

Execution Sample

DSA Typescript

maxHeap = new MaxHeap()
minHeap = new MinHeap()
addNum(num) {
  if (maxHeap.isEmpty() || num <= maxHeap.peek()) maxHeap.insert(num)
  else minHeap.insert(num)
  balanceHeaps()
}
getMedian() {
  if (maxHeap.size() > minHeap.size()) return maxHeap.peek()
  if (minHeap.size() > maxHeap.size()) return minHeap.peek()
  return (maxHeap.peek() + minHeap.peek()) / 2
}

Add numbers to two heaps and balance them to find median efficiently.

Execution Table

Step	Operation	Number Added	Max-Heap Nodes	Min-Heap Nodes	Balance Action	Median
1	Add number	5	[5]	[]	No balance needed	5
2	Add number	15	[5]	[15]	No balance needed	10
3	Add number	1	[5,1]	[15]	No balance needed	5
4	Add number	3	[3,1]	[5,15]	Moved 5 from max to min	4
5	Add number	8	[5,1,3]	[8,15]	Moved 5 from min to max	5
6	Add number	7	[5,1,3]	[7,8,15]	No balance needed	6
7	Add number	9	[7,5,3,1]	[8,9,15]	Moved 7 from min to max	7
8	Add number	10	[7,5,3,1]	[8,9,10,15]	No balance needed	7.5
9	Add number	6	[7,6,3,1,5]	[8,9,10,15]	No balance needed	7
Exit	Stream ended	-	[7,6,3,1,5]	[8,9,10,15]	Balanced heaps	7

💡 All numbers processed; heaps balanced; median computed.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	Final
maxHeap	[]	[5]	[5]	[5,1]	[3,1]	[5,1,3]	[5,1,3]	[7,5,3,1]	[7,5,3,1]	[7,6,3,1,5]	[7,6,3,1,5]
minHeap	[]	[]	[15]	[15]	[5,15]	[8,15]	[7,8,15]	[8,9,15]	[8,9,10,15]	[8,9,10,15]	[8,9,10,15]
median	-	5	10	5	4	5	6	7	7.5	7	7

Key Moments - 3 Insights

Why do we add the new number to max-heap if it is less than or equal to max-heap root?

Because max-heap stores the smaller half of numbers, so numbers less or equal to its root belong there. See execution_table step 1 and 3 where 5 and 1 go to max-heap.

Why do we balance heaps when their size difference is more than 1?

To keep the median calculation correct, heaps must be balanced or differ by only one element. See step 4 where 5 moves from max to min to balance sizes.

How is median calculated when heaps have equal size?

Median is average of roots of both heaps. See step 2 and 8 where median is (5+15)/2=10 and (7+8)/2=7.5 respectively.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which number was moved to balance the heaps?

A 5

B 3

C 1

D 15

💡 Hint

Check the 'Balance Action' column at step 4 in execution_table.

At which step does the median become 7.5 according to the execution_table?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look at the 'Median' column in execution_table for value 7.5.

If the new number 20 is added after step 9, where will it be inserted?

A max-heap

B min-heap

C Either heap

D Neither heap

💡 Hint

Compare 20 with max-heap root 7 in variable_tracker after step 9.

Concept Snapshot

Median of Data Stream Using Two Heaps:
- Use max-heap for lower half, min-heap for upper half
- Add new number to appropriate heap
- Balance heaps if size difference > 1
- Median is root of larger heap or average of roots if equal size
- Efficient for streaming data median calculation

Full Transcript

This concept uses two heaps to find the median of a stream of numbers efficiently. The max-heap stores the smaller half of numbers, and the min-heap stores the larger half. When a new number arrives, it is compared with the max-heap root to decide which heap to insert into. After insertion, heaps are balanced to ensure their sizes differ by at most one. The median is then calculated as the root of the larger heap or the average of both roots if heaps are equal in size. The execution table shows step-by-step how numbers are added, heaps balanced, and median updated. The variable tracker records the state of heaps and median after each step. Key moments clarify why numbers go to specific heaps, why balancing is needed, and how median is computed. The visual quiz tests understanding of heap balancing and median calculation steps.

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