Median of Data Stream Using Two Heaps in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using two heaps to find the median of a data stream?

Use a max-heap to store the smaller half of numbers and a min-heap to store the larger half. This way, the median is either the top of one heap or the average of the tops of both heaps.

beginner

Why do we balance the sizes of the two heaps when finding the median?

Balancing ensures that the heaps differ in size by at most one, so the median can be found easily from the top elements of the heaps.

beginner

In the two heaps approach, which heap stores the smaller half of the numbers?

The max-heap stores the smaller half of the numbers, so its top is the largest of the smaller half.

intermediate

How do you find the median when the total number of elements is even using two heaps?

The median is the average of the top elements of the max-heap and min-heap.

intermediate

What happens when a new number is smaller than the max-heap's top in the two heaps method?

The number is added to the max-heap because it belongs to the smaller half of the data stream.

What data structure is used to store the larger half of the numbers in the two heaps method?

A Max-heap

B Min-heap

C Queue

D Stack

The min-heap stores the larger half of the numbers so that the smallest of the larger half is at the top.

When the total number of elements is odd, where does the extra element go in the two heaps method?

A Either heap, but usually the max-heap

B Min-heap

C Neither heap

D Max-heap

The extra element can be in either heap, but commonly it is kept in the max-heap to simplify median calculation.

What is the time complexity to add a number and find the median using two heaps?

A O(1)

B O(n)

C O(log n)

D O(n log n)

Adding a number and balancing heaps takes O(log n), and finding the median is O(1).

If the new number is greater than the top of the max-heap, where should it be added?

A Min-heap

B Both heaps

C Max-heap

D Discarded

Numbers greater than the max-heap top belong to the larger half, so they go into the min-heap.

What do you do if the heaps become unbalanced after insertion?

A Clear both heaps

B Remove elements from both heaps

C Ignore the imbalance

D Move the top element from the larger heap to the smaller heap

To keep heaps balanced, move the top element from the bigger heap to the smaller heap.

Explain how two heaps are used to find the median in a data stream.

Think about splitting numbers into two groups and how their tops help find the middle.

Describe the steps to insert a new number into the two heaps and maintain the median.

Focus on where the number goes and how to keep heaps balanced.

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