Median of Data Stream Using Two Heaps in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to add a number to the max heap.

DSA C#

maxHeap.[1](num);

Drag options to blanks, or click blank then click option'

AAdd

BPush

CInsert

DEnqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'Add' which is not a method for heap insertion here.

Using 'Insert' which is not defined for this heap.

Using 'Enqueue' which is for queues, not heaps.

In this implementation, the max heap uses the method Push to add elements.

2fill in blank

medium

Complete the code to balance the heaps when max heap has more elements.

DSA C#

if (maxHeap.Count > minHeap.Count + [1]) {
    minHeap.Push(maxHeap.Pop());
}

Drag options to blanks, or click blank then click option'

A1

B0

C2

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 which causes unnecessary balancing.

Using 2 or 3 which delays balancing too much.

We balance heaps when max heap has more than one extra element compared to min heap.

3fill in blank

hard

Fix the error in the code to get the median when heaps are balanced.

DSA C#

return (maxHeap.Peek() + minHeap.[1]()) / 2.0;

Drag options to blanks, or click blank then click option'

APop

BFront

CPeek

DTop

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'Pop' removes elements, which is incorrect here.

Using 'Top' or 'Front' which are not standard heap methods.

To get the median without removing elements, use Peek on both heaps.

4fill in blank

hard

Fill both blanks to correctly add a number to the appropriate heap.

DSA C#

if (minHeap.Count > 0 && num > minHeap.[1]()) {
    minHeap.[2](num);
} else {
    maxHeap.Push(num);
}

Drag options to blanks, or click blank then click option'

APeek

BPop

CPush

DAdd

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'Pop' to check removes the element, which is wrong.

Using 'Add' which is not the heap insertion method here.

We compare with the smallest element in minHeap using Peek and add to minHeap using Push.

5fill in blank

hard

Fill all three blanks to correctly rebalance heaps and return the median.

DSA C#

if (maxHeap.Count > minHeap.Count + [1]) {
    minHeap.Push(maxHeap.[2]());
} else if (minHeap.Count > maxHeap.Count + [3]) {
    maxHeap.Push(minHeap.Pop());
}

if (maxHeap.Count == minHeap.Count) {
    return (maxHeap.Peek() + minHeap.Peek()) / 2.0;
} else {
    return maxHeap.Peek();
}

Drag options to blanks, or click blank then click option'

A1

BPop

DPeek

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'Peek' instead of 'Pop' when moving elements causes duplicates.

Using size difference other than 1 causes incorrect balancing.

We rebalance when size difference is more than 1. We move elements using Pop from maxHeap and add to minHeap. The same size difference check applies for minHeap.

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