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

Concept Flow - Median of Data Stream Using Two Heaps

New number arrives

↓

Compare with max-heap top

↓

Add to max-heap

↓

Balance heaps size

↓

Calculate median

↓

Output median

New numbers go to max-heap or min-heap based on comparison. Heaps are balanced to keep sizes close. Median is top of max-heap or average of tops.

Execution Sample

DSA C#

AddNum(10)
AddNum(20)
AddNum(30)
FindMedian()

Add numbers 10, 20, 30 to heaps and find median after all insertions.

Execution Table

Step	Operation	Number Added	Max-Heap (Lower Half)	Min-Heap (Upper Half)	Balance Action	Median
1	AddNum	10	[10]	[]	No balancing needed	10
2	AddNum	20	[10]	[20]	No balancing needed	15.0
3	AddNum	30	[10, 20]	[30]	Moved 20 from min-heap to max-heap to balance	20
4	FindMedian	-	[10, 20]	[30]	No action	20

💡 All numbers added and heaps balanced; median found.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
maxHeap	[]	[10]	[10]	[10, 20]	[10, 20]
minHeap	[]	[]	[20]	[30]	[30]
median	N/A	10	15.0	20	20

Key Moments - 3 Insights

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

Because max-heap stores the smaller half of numbers, so numbers less or equal to its top belong there. See execution_table step 1 where 10 is added to max-heap.

Why do we balance heaps after each insertion?

To keep the size difference at most 1, ensuring median calculation is correct. See execution_table step 3 where balancing moves 20 from min-heap to max-heap.

How is median calculated when heaps have equal size?

Median is average of max-heap top and min-heap top. See execution_table step 2 where median is (10 + 20)/2 = 15.0.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the median?

A 10

B 15.0

C 20

D 30

💡 Hint

Check the Median column at step 2 in execution_table.

At which step does balancing move an element between heaps?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the Balance Action column in execution_table.

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

A Max-heap

B Min-heap

C Either heap

D Neither heap

💡 Hint

Refer to concept_flow and key_moments about where smaller numbers go.

Concept Snapshot

Use two heaps: max-heap for lower half, min-heap for upper half.
Add new number to max-heap if <= max-heap top, else min-heap.
Balance heaps sizes to differ by at most 1.
Median is max-heap top if odd count, else average of tops.
Efficient for streaming data median calculation.

Full Transcript

This concept uses two heaps to find the median of a stream of numbers efficiently. When a new number arrives, it is compared with the top of the max-heap (which stores the smaller half of numbers). If the number is smaller or equal, it goes to the max-heap; otherwise, it goes to the min-heap (which stores the larger half). After each insertion, the heaps are balanced so their sizes differ by at most one. The median is then either the top of the max-heap (if odd total numbers) or the average of the tops of both heaps (if even total numbers). This approach allows quick median calculation as numbers stream in.

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 remove duplicates from the data stream

B. To sort the entire data stream before finding the median

C. To store all data in one heap for quick access

D. To efficiently find the median by balancing smaller and larger halves of the data

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: How this helps find the median

   By balancing these heaps, the median is either the top of one heap or the average of both tops.

3. Final Answer:

   To efficiently find the median by balancing smaller and larger halves of the data -> Option D

4. Quick Check:

   Two heaps balance halves = median found efficiently [OK]

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

Common Mistakes:

• Thinking heaps sort all data fully
• Using only one heap for median
• Confusing median with mean

2. Which of the following C# code snippets correctly declares a max-heap using PriorityQueue for the Median of Data Stream problem?

easy

A. var maxHeap = new PriorityQueue();

B. var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => b - a));

C. var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => a - b));

D. var maxHeap = new PriorityQueue(Comparer<int>.Default);

Solution

1. Step 1: Understand PriorityQueue default behavior

   By default, PriorityQueue in C# is a min-heap based on priority values.

2. Step 2: Creating a max-heap requires reversing comparison

   Using Comparer<int>.Create((a, b) => b - a) reverses order to make a max-heap.

3. Final Answer:

   var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a)); -> Option B

4. Quick Check:

   Reverse comparer creates max-heap [OK]

Hint: Reverse comparer for max-heap in C# PriorityQueue [OK]

Common Mistakes:

• Using default comparer creates min-heap, not max-heap
• Confusing type parameters in PriorityQueue
• Not providing comparer for max-heap

3. Given the following sequence of numbers added to the data stream: 5, 15, 1, 3, what is the median after all insertions using two heaps approach?

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 -> maxHeap=[5]; 15 -> minHeap=[15]; 1 ≤ max.top(5) -> maxHeap=[5,1] top=5; 3 ≤5 -> maxHeap=[5,1,3] top=5 (size 3 vs 1). Balance: move max.top=5 to minHeap -> maxHeap=[3,1] top=3, minHeap=[15,5] top=5.

2. Step 2: Calculate median from heaps

   maxHeap top = 3, minHeap top = 5. Median = (3 + 5) / 2 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

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

Hint: Median is average of two middle values when even count [OK]

Common Mistakes:

• Not balancing heaps after each insertion
• Taking median as middle element without averaging
• Mixing up maxHeap and minHeap tops

4. Consider this buggy C# code snippet for adding a number to the two heaps. What is the main error?

if (maxHeap.Count == 0 || num <= maxHeap.Peek())
    maxHeap.Enqueue(num, num);
else
    minHeap.Enqueue(num, num);

// Balance heaps
if (maxHeap.Count > minHeap.Count + 1)
    minHeap.Enqueue(maxHeap.Dequeue(), maxHeap.Dequeue());
else if (minHeap.Count > maxHeap.Count)
    maxHeap.Enqueue(minHeap.Dequeue(), minHeap.Dequeue());

medium

A. Enqueue uses wrong priority values

B. Using <= instead of < causes wrong heap insertion

C. Calling Dequeue() twice when balancing heaps causes errors

D. Not checking if heaps are empty before Peek()

Solution

1. Step 1: Analyze balancing code

   When balancing, code calls Dequeue() twice to move one element, which removes two elements incorrectly.

2. Step 2: Correct balancing approach

   Only one Dequeue() should be called to move one element from one heap to the other.

3. Final Answer:

   Calling Dequeue() twice when balancing heaps causes errors -> Option C

4. Quick Check:

   Double Dequeue removes two elements instead of one [OK]

Hint: Balance heaps by moving one element, not two [OK]

Common Mistakes:

• Calling Dequeue twice instead of once
• Ignoring heap size difference rules
• Incorrect comparison operators for insertion

5. You have a data stream of integers where duplicates are allowed. How does the two heaps approach handle duplicates when calculating the median, and what is the median after inserting [2, 2, 3, 4, 4, 4]?

hard

A. Duplicates are stored normally; median is 3.5

B. Duplicates are ignored; median is 2

C. Duplicates cause errors; median cannot be found

D. Duplicates are stored only once; median is 4

Solution

1. Step 1: Understand handling of duplicates in heaps

   Duplicates are stored like any other number; heaps do not remove duplicates automatically.

2. Step 2: Insert numbers and find median

   Numbers: [2, 2, 3, 4, 4, 4]. Sorted: [2, 2, 3, 4, 4, 4]. Median is average of 3rd and 4th elements: (3 + 4) / 2 = 3.5.

3. Final Answer:

   Duplicates are stored normally; median is 3.5 -> Option A

4. Quick Check:

   Duplicates stored; median of [2,2,3,4,4,4] = 3.5 [OK]

Hint: Duplicates do not affect heap logic; median from sorted data [OK]

Common Mistakes:

• Assuming duplicates are removed automatically
• Calculating median incorrectly with duplicates
• Confusing median with mode