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

Concept Flow - Median of Data Stream Using Two Heaps

New number arrives

↓

Compare with maxHeap top?

↓

Add to maxHeap

↓

Balance heaps size?

↓

If size difference > 1

↓

Move root from bigger heap to smaller heap

↓

Calculate median

↓

Return median

New numbers go into one of two heaps (maxHeap for smaller half, minHeap for larger half). We keep heaps balanced, then median is top(s) of heaps.

Execution Sample

DSA Javascript

class MedianFinder {
  constructor() {
    this.maxHeap = new MaxHeap();
    this.minHeap = new MinHeap();
  }
  addNum(num) {
    // add number logic
  }
  findMedian() {
    // median logic
  }
}

This class adds numbers to two heaps and finds median efficiently.

Execution Table

Step	Operation	Number Added	MaxHeap Nodes	MinHeap Nodes	Balance Action	Median Calculation	Visual State
1	Add number	5	[5]	[]	No balance needed	Median = 5	MaxHeap: [5], MinHeap: []
2	Add number	2	[5, 2]	[]	Balance: Move 5 to MinHeap	Median = (2 + 5)/2 = 3.5	MaxHeap: [2], MinHeap: [5]
3	Add number	10	[2]	[5, 10]	Balance: Move 5 to MaxHeap	Median = 5	MaxHeap: [5, 2], MinHeap: [10]
4	Add number	1	[5, 2, 1]	[10]	No balance needed	Median = (2 + 5)/2 = 3.5	MaxHeap: [5, 2, 1], MinHeap: [10]
5	Add number	3	[5, 3, 1, 2]	[10]	Balance: Move 5 to MinHeap	Median = 3	MaxHeap: [3, 2, 1], MinHeap: [5, 10]
6	Add number	8	[3, 2, 1]	[5, 10, 8]	Balance: Move 5 to MaxHeap	Median = 5	MaxHeap: [5, 3, 1, 2], MinHeap: [8, 10]
7	Add number	7	[5, 3, 1, 2]	[7, 8, 10]	Balance: Move 7 to MaxHeap	Median = (5 + 7)/2 = 6	MaxHeap: [7, 5, 1, 2, 3], MinHeap: [8, 10]
8	Add number	6	[7, 6, 1, 2, 3, 5]	[8, 10]	No balance needed	Median = 6	MaxHeap: [7, 6, 1, 2, 3, 5], MinHeap: [8, 10]
9	Add number	4	[7, 6, 4, 2, 3, 5, 1]	[8, 10]	Balance: Move 7 to MinHeap	Median = (6 + 7)/2 = 6.5	MaxHeap: [6, 5, 4, 2, 3, 1], MinHeap: [7, 8, 10]
10	Add number	9	[6, 5, 4, 2, 3, 1]	[7, 8, 10, 9]	Balance: Move 7 to MaxHeap	Median = 7	MaxHeap: [7, 6, 4, 2, 3, 1, 5], MinHeap: [8, 9, 10]
11	Stop	-	[7, 6, 4, 2, 3, 1, 5]	[8, 9, 10]	Heaps balanced	Median = 7	Final state

💡 All numbers added and heaps balanced; median calculated at each step.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
maxHeap	[]	[5]	[2]	[2]	[5,2,1]	[3,2,1]	[3,2,1]	[7,5,1,2,3]	[7,6,1,2,3,5]	[6,5,4,2,3,1]	[7,6,4,2,3,1,5]	[7,6,4,2,3,1,5]
minHeap	[]	[]	[5]	[5,10]	[10]	[10]	[8,10]	[8,10]	[7,8,10]	[8,9,10]	[8,9,10]	[8,9,10]
median	N/A	5	3.5	5	3.5	3	5	6	6	6.5	7	7

Key Moments - 3 Insights

Why do we move elements between heaps after adding a number?

Because heaps must be balanced in size (difference at most 1) to correctly find the median. See execution_table rows 2, 3, 5, 6 where balance actions move elements.

Why do we add smaller numbers to maxHeap and larger to minHeap?

MaxHeap stores the smaller half so its top is the largest of the smaller numbers; MinHeap stores larger half so its top is smallest of larger numbers. This split helps find median quickly. See concept_flow and execution_table steps.

How is median calculated when heaps have equal size vs different sizes?

If heaps are equal size, median is average of both tops (rows 2,5,9). If one heap is bigger, median is top of that heap (rows 1,3,4,6,8,10).

Visual Quiz - 3 Questions

Look at execution_table row 5, what is the median after adding number 3?

A 4

B 3

C 5

D 3.5

💡 Hint

Check the 'Median Calculation' column in row 5 of execution_table.

At which step does the maxHeap first contain 7 elements?

A Step 9

B Step 10

C Step 7

D Step 11

💡 Hint

Look at 'MaxHeap Nodes' column in execution_table rows for size changes.

If we add a number smaller than all existing numbers, which heap will it go to initially?

A minHeap

B Either heap randomly

C maxHeap

D Neither heap

💡 Hint

Refer to concept_flow: smaller numbers go to maxHeap.

Concept Snapshot

Median of Data Stream Using Two Heaps:
- Use maxHeap for smaller half, minHeap for larger half
- Add new number to correct heap based on comparison
- Balance heaps sizes (difference ≤ 1)
- Median is top of bigger heap or average of both tops
- Efficient for streaming data median calculation

Full Transcript

This concept uses two heaps to find the median of a stream of numbers efficiently. New numbers are added to either a maxHeap (holding smaller half) or a minHeap (holding larger half). After each addition, heaps are balanced so their sizes differ by at most one. The median is then either the top of the bigger heap or the average of both tops if sizes are equal. The execution table shows step-by-step how numbers are added, heaps balanced, and median calculated. The variable tracker records heap contents and median after each step. Key moments clarify why balancing is needed, how numbers are assigned to heaps, and how median is computed. The visual quiz tests understanding of median values and heap sizes at specific steps.