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.