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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a number into the max heap.

DSA C++

maxHeap.[1](num);

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

Aempty

Bpop

Ctop

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push to add elements.

Trying to access top instead of inserting.

We use push to add a new element to the heap.

2fill in blank

medium

Complete the code to balance the sizes of the two heaps after insertion.

DSA C++

if (maxHeap.size() > minHeap.size() + [1]) {
    minHeap.push(maxHeap.top());
    maxHeap.pop();
}

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

A0

B2

C1

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 2 instead of 1 for size difference.

Not balancing heaps after insertion.

We balance heaps when maxHeap size is more than minHeap size by 1.

3fill in blank

hard

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

DSA C++

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

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

AminHeap

BmaxHeap

Cheap

DmedianHeap

Attempts:

3 left

💡 Hint

Common Mistakes

Using maxHeap.top() twice.

Using undefined heap names.

The median is average of tops of maxHeap and minHeap, so use minHeap.

4fill in blank

hard

Fill both blanks to insert a number into the correct heap based on its value.

DSA C++

if (maxHeap.empty() || num [1] maxHeap.top()) {
    maxHeap.[2](num);
} else {
    minHeap.push(num);
}

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

A<

B>

Cpush

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < for comparison.

Using pop instead of push to insert.

If number is less than maxHeap top, insert into maxHeap using push.

5fill in blank

hard

Fill all three blanks to return the median correctly based on heap sizes.

DSA C++

if (maxHeap.size() > minHeap.size()) {
    return maxHeap.[1]();
} else if (minHeap.size() > maxHeap.size()) {
    return minHeap.[2]();
} else {
    return (maxHeap.top() + minHeap.top()) / [3];
}

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

Atop

C2.0

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using size() instead of top() to get element.

Dividing by 2 instead of 2.0 causing integer division.

Return top of the bigger heap or average of both tops divided by 2.0.

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 efficiently find the median by balancing smaller and larger halves of the data

B. To sort the entire data stream in ascending order

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

D. To remove duplicate elements from the data stream

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: Explain how median is found

   Balancing these heaps allows quick access to the middle values, enabling efficient median calculation.

3. Final Answer:

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

4. Quick Check:

   Two heaps balance halves = median found fast [OK]

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

Common Mistakes:

• Thinking heaps sort entire data
• Using one heap only
• Confusing heaps with arrays

2. Which of the following is the default way to declare a max-heap in C++ using the priority_queue?

easy

A. priority_queue maxHeap;

B. priority_queue<int> maxHeap;

C. priority_queue maxHeap;

D. priority_queue maxHeap;

Solution

1. Step 1: Recall default priority_queue behavior

   By default, priority_queue in C++ is a max-heap using less<int>.

2. Step 2: Identify correct declaration

   Declaring priority_queue<int> maxHeap; creates a max-heap without extra parameters.

3. Final Answer:

   priority_queue<int> maxHeap; -> Option B

4. Quick Check:

   Default priority_queue = max-heap [OK]

Hint: Default priority_queue is max-heap [OK]

Common Mistakes:

• Using greater<int> for max-heap
• Omitting vector container
• Confusing max-heap with min-heap syntax

3. Consider the following C++ code snippet that inserts numbers into two heaps to find the median:

priority_queue<int> maxHeap;
priority_queue minHeap;

// Insert 10
maxHeap.push(10);
// Insert 20
minHeap.push(20);
// Insert 15
if (15 <= maxHeap.top()) maxHeap.push(15); else minHeap.push(15);

// Balance heaps
if (maxHeap.size() > minHeap.size() + 1) {
  minHeap.push(maxHeap.top());
  maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
  maxHeap.push(minHeap.top());
  minHeap.pop();
}

// Calculate median
if (maxHeap.size() == minHeap.size())
  cout << (maxHeap.top() + minHeap.top()) / 2.0 << endl;
else
  cout << maxHeap.top() << endl;

What is the output of this code?

medium

A. 15

B. 15.0

C. 12.5

D. 20

Solution

1. Step 1: Insert elements and balance heaps

   Insert 10 into maxHeap: maxHeap = [10]. Insert 20 into minHeap: minHeap = [20]. Insert 15: 15 > 10, so goes to minHeap: minHeap = [15, 20]. Balance heaps: minHeap size (2) > maxHeap size (1), so move minHeap top (15) to maxHeap. Now maxHeap = [15, 10], minHeap = [20].

2. Step 2: Calculate median

   maxHeap size = 2, minHeap size = 1, so median is maxHeap.top() = 15. Sizes unequal, cout << maxHeap.top() << endl; outputs 15.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Median after balancing = 15 [OK]

Hint: Balance heaps, median = top of larger heap or average [OK]

Common Mistakes:

• Not balancing heaps correctly
• Integer division instead of float
• Wrong heap insertion condition

4. The following code snippet is intended to maintain two heaps for median calculation. Identify the bug:

priority_queue<int> maxHeap;
priority_queue minHeap;

void addNumber(int num) {
  if (maxHeap.empty() || num <= maxHeap.top()) {
    maxHeap.push(num);
  } else {
    minHeap.push(num);
  }

  if (maxHeap.size() > minHeap.size()) {
    minHeap.push(maxHeap.top());
    maxHeap.pop();
  } else if (minHeap.size() > maxHeap.size() + 1) {
    maxHeap.push(minHeap.top());
    minHeap.pop();
  }
}

medium

A. The heaps are not declared correctly for median calculation

B. The comparison operator in if condition should be num >= maxHeap.top()

C. The balancing condition for maxHeap is incorrect; it should check if maxHeap.size() > minHeap.size() + 1

D. The function does not insert elements into any heap

Solution

1. Step 1: Analyze balancing conditions

   The code moves element from maxHeap to minHeap if maxHeap.size() > minHeap.size(), but it should only do so if maxHeap.size() > minHeap.size() + 1 to keep heaps balanced properly.

2. Step 2: Confirm correct balancing logic

   Proper balancing ensures size difference is at most 1. The current condition causes unnecessary moves, breaking balance.

3. Final Answer:

   The balancing condition for maxHeap is incorrect; it should check if maxHeap.size() > minHeap.size() + 1 -> Option C

4. Quick Check:

   Balance heaps only if size difference > 1 [OK]

Hint: Balance heaps only if size difference > 1 [OK]

Common Mistakes:

• Wrong balancing condition
• Swapping heap roles
• Incorrect comparison operators

5. You are given a stream of integers: [5, 15, 1, 3, 8, 7, 9, 10, 6, 11]. Using two heaps to find the median after each insertion, what is the median after inserting all elements?

hard

A. 8

B. 7

C. 6.5

D. 7.5

Solution

1. Step 1: Insert elements and balance heaps step-by-step

   After processing the entire stream with proper insertion (to maxHeap if <= max.top or empty, else minHeap) and balancing (rebalance if max.size > min.size + 1 or min.size > max.size), final state: maxHeap size=5 (top=7), minHeap size=5 (top=8).

2. Step 2: Calculate final median

   After all insertions, maxHeap size = 5, minHeap size = 5, median = average of tops: (7 + 8) / 2 = 7.5

3. Final Answer:

   7.5 -> Option D

4. Quick Check:

   Median after all insertions = 7.5 [OK]

Hint: Median = average of two heap tops if equal size [OK]

Common Mistakes:

• Not balancing heaps after each insertion
• Calculating median from wrong heap
• Forgetting to average when heaps equal size