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

Concept Flow - Median of Data Stream Using Two Heaps

Start

↓

New number arrives

↓

Compare with max-heap root

↓

Insert into max-heap

↓

Insert into min-heap

↓

Balance heaps sizes

↓

Calculate median

↓

Output median

↓

Wait for next number

New numbers go into one of two heaps (max-heap for smaller half, min-heap for larger half). Heaps are balanced to keep sizes close. Median is from roots of heaps.

Execution Sample

DSA Go

maxHeap = []
minHeap = []
AddNum(num):
  if maxHeap empty or num <= maxHeap[0]:
    push maxHeap num
  else:
    push minHeap num
  balance heaps
  median = compute median

Add numbers to two heaps, balance them, then find median from heap tops.

Execution Table

Step	Operation	Number Added	Max-Heap Nodes	Min-Heap Nodes	Balance Action	Median	Visual State
1	Add number	5	[5]	[]	No balance needed	5	Max-Heap: 5 Min-Heap:
2	Add number	2	[5, 2]	[]	Balance: move maxHeap root to minHeap	3.5	Max-Heap: 2 Min-Heap: 5
3	Add number	10	[2]	[5, 10]	Balance: move minHeap root to maxHeap	5	Max-Heap: 5, 2 Min-Heap: 10
4	Add number	1	[5, 2, 1]	[10]	No balance needed	3.5	Max-Heap: 5, 2, 1 Min-Heap: 10
5	Add number	3	[5, 3, 1, 2]	[10]	Balance: move maxHeap root to minHeap	5	Max-Heap: 3, 2, 1 Min-Heap: 5, 10
6	Add number	8	[3, 2, 1]	[5, 10, 8]	Balance: move minHeap root to maxHeap	5.5	Max-Heap: 5, 3, 1, 2 Min-Heap: 8, 10
7	Add number	7	[5, 3, 1, 2]	[7, 10, 8]	No balance needed	5.5	Max-Heap: 5, 3, 1, 2 Min-Heap: 7, 10, 8
8	Add number	6	[5, 3, 1, 2, 6]	[7, 10, 8]	Balance: move maxHeap root to minHeap	6	Max-Heap: 6, 5, 1, 2, 3 Min-Heap: 7, 10, 8
9	Add number	4	[6, 5, 1, 2, 3]	[4, 7, 8, 10]	Balance: move minHeap root to maxHeap	5.5	Max-Heap: 6, 5, 4, 2, 3, 1 Min-Heap: 7, 10, 8
10	Add number	9	[6, 5, 4, 2, 3, 1]	[7, 9, 8, 10]	No balance needed	6	Max-Heap: 6, 5, 4, 2, 3, 1 Min-Heap: 7, 9, 8, 10
11	Termination	-	[6, 5, 4, 2, 3, 1]	[7, 9, 8, 10]	Heaps balanced within 1 size difference	6	Final median after all insertions

💡 All numbers processed; heaps balanced; median computed from heap tops.

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]	[5, 2]	[5, 2, 1]	[3, 2, 1]	[5, 3, 1, 2]	[5, 3, 1, 2]	[6, 5, 1, 2, 3]	[6, 5, 4, 2, 3, 1]	[6, 5, 4, 2, 3, 1]	[6, 5, 4, 2, 3, 1]
minHeap	[]	[]	[5]	[5, 10]	[10]	[5, 10]	[8, 10]	[7, 10, 8]	[7, 10, 8]	[4, 7, 8, 10]	[7, 9, 8, 10]	[7, 9, 8, 10]
median	-	5	3.5	5	3.5	5	5.5	5.5	6	5.5	6	6

Key Moments - 3 Insights

Why do we move the root element from one heap to another during balancing?

Because heaps must have sizes differing by at most 1 to correctly find the median. Moving the root (smallest or largest) keeps the halves balanced, as shown in steps 2, 3, 5, 6, and 9 in the execution_table.

Why do we compare the new number with the max-heap root to decide where to insert?

The max-heap root holds the largest number in the smaller half. If the new number is smaller or equal, it belongs to the smaller half (max-heap). Otherwise, it goes to the min-heap. This is shown in the operations column of the execution_table.

How is the median calculated when heaps have different sizes?

If heaps sizes differ by 1, median is the root of the larger heap. If equal, median is average of both roots. This is visible in the median column of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the median after adding number 1?

A 3.5

B 5

C 2

D 1

💡 Hint

Check the 'Median' column at step 4 in the execution_table.

At which step does the min-heap first get an element?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Min-Heap Nodes' column to see when min-heap changes from empty.

If we add a number smaller than all existing numbers, where will it be inserted?

A Either heap randomly

B Min-Heap

C Max-Heap

D It will replace the root of max-heap

💡 Hint

Refer to the 'Operation' and 'Number Added' columns and the rule comparing with max-heap root.

Concept Snapshot

Median of Data Stream Using Two Heaps:
- Use max-heap for smaller half, min-heap for larger half
- Insert new number into correct heap by comparing with max-heap root
- Balance heaps so size difference ≤ 1
- Median is root of larger heap or average of both roots
- Efficient for continuous median calculation in data streams

Full Transcript

This concept uses two heaps to find the median of a stream of numbers efficiently. One heap (max-heap) stores the smaller half of numbers, and the other (min-heap) stores the larger half. When a new number arrives, it is compared with the root of the max-heap to decide where to insert. After insertion, heaps are balanced to keep their sizes close. The median is then calculated from the roots of the heaps. This method allows quick median updates as numbers stream in.