Median of Data Stream Using Two Heaps in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the median after inserting these numbers?

Consider a data stream where numbers are inserted one by one. Using two heaps (a max-heap for the lower half and a min-heap for the upper half), what is the median after inserting the numbers 5, 15, 1, 3 in this order?

DSA C#

Insert 5
Insert 15
Insert 1
Insert 3
Find median

A 4.0

B 3.0

C 5.0

D 6.0

💡 Hint

Remember to balance the heaps after each insertion and calculate median based on heap sizes.

After inserting 5 and 15, the median is (5 + 15)/2 = 10. After inserting 1, median is 5. After inserting 3, the two heaps are balanced and the median is (3 + 5)/2 = 4.0.

🧠 Conceptual

intermediate

Why use two heaps for median in a data stream?

Why is it efficient to use two heaps (a max-heap and a min-heap) to find the median of a data stream?

A Because two heaps allow balancing lower and upper halves, enabling O(log n) insertion and O(1) median retrieval.

B Because two heaps allow constant time insertion and median retrieval.

C Because two heaps reduce memory usage by storing only half the elements each.

D Because two heaps store all elements sorted, so median is always at the root of one heap.

💡 Hint

Think about how heaps help keep track of halves of the data.

Two heaps split the data into lower and upper halves. Max-heap stores the smaller half, min-heap stores the larger half. Balancing them keeps insertion O(log n) and median retrieval O(1).

🔧 Debug

advanced

Identify the error in this median calculation code snippet

Given the following C# code snippet for inserting a number into two heaps and calculating median, what error will occur?

DSA C#

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

if (maxHeap.Count > minHeap.Count + 1)
    minHeap.Add(maxHeap.ExtractMax());
else if (minHeap.Count > maxHeap.Count)
    maxHeap.Add(minHeap.ExtractMin());

return (maxHeap.Count == minHeap.Count) ? (maxHeap.Peek() + minHeap.Peek()) / 2 : maxHeap.Peek();

A ExtractMax and ExtractMin methods do not exist in C# heaps.

B Integer division causes incorrect median when counts are equal.

C The condition to rebalance heaps is incorrect and causes infinite loop.

D The code does not handle empty heaps before calling Peek.

💡 Hint

Check how division works in C# when both operands are integers.

In C#, dividing two integers performs integer division, truncating decimals. So when counts are equal, the median calculation (maxHeap.Peek() + minHeap.Peek()) / 2 returns an integer, losing the decimal part.

❓ Predict Output

advanced

What is the median after these insertions?

Using two heaps, what is the median after inserting the numbers 2, 4, 7, 1, 5, 3 in this order?

DSA C#

Insert 2
Insert 4
Insert 7
Insert 1
Insert 5
Insert 3
Find median

A 3.0

B 4.0

C 3.5

D 4.5

💡 Hint

Balance heaps after each insertion and calculate median based on heap sizes.

After all insertions, the two heaps are balanced with equal size. Median is average of max-heap top (3) and min-heap top (4), so (3 + 4)/2 = 3.5.

🧠 Conceptual

expert

What is the time complexity of finding median in a data stream using two heaps?

Given a data stream where numbers are inserted one by one and median is found after each insertion using two heaps, what is the time complexity per insertion and median retrieval?

A Insertion: O(1), Median retrieval: O(n)

B Insertion: O(n), Median retrieval: O(log n)

C Insertion: O(log n), Median retrieval: O(log n)

D Insertion: O(log n), Median retrieval: O(1)

💡 Hint

Consider heap insertion and peek operations.

Insertion into a heap is O(log n) due to reheapifying. Median retrieval is O(1) because it is the top element(s) of the heaps.

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