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 can be quickly found from the tops of the heaps.

beginner

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

Balancing ensures that the heaps represent equal halves of the data or differ by one element, which helps in correctly calculating the median.

beginner

In the two heaps method, what does the max-heap store?

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

intermediate

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

The median is the top element of the heap that has one extra element (either max-heap or min-heap).

intermediate

What is the time complexity of adding a number and finding the median using two heaps?

Adding a number takes O(log n) due to heap insertion, and finding the median is O(1) because it is the top element(s) of the heaps.

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

A Min-heap

B Max-heap

C Queue

D Stack

The larger half of the numbers is stored in a min-heap so that the smallest number in the larger half is easily accessible.

If the max-heap has 5 elements and the min-heap has 3 elements, what should you do?

A Move the top element from min-heap to max-heap

B Move the top element from max-heap to min-heap

C Add a new element to min-heap

D Do nothing

The heaps should be balanced or differ by at most one element. Moving the top element from max-heap to min-heap balances the sizes.

What is the median when both heaps have the same number of elements?

A Average of tops of max-heap and min-heap

B Top of min-heap

C Top of max-heap

D Sum of all elements

When heaps are equal in size, the median is the average of the two middle values, which are the tops of the two heaps.

Why is a max-heap used for the smaller half instead of a min-heap?

A To store negative numbers

B To sort numbers in ascending order

C Because min-heap is slower

D To quickly access the largest number in the smaller half

A max-heap allows quick access to the largest number in the smaller half, which helps in balancing and median calculation.

What is the first step when adding a new number to the data stream using two heaps?

A Add to max-heap always

B Add to min-heap always

C Add to max-heap if number is smaller than or equal to max-heap top

D Add to min-heap if number is smaller than max-heap top

The new number is compared with the max-heap top to decide which heap it belongs to, ensuring correct partitioning.

Explain how two heaps are used to maintain the median of a data stream.

Think about dividing numbers into two parts and how to find middle values quickly.

Describe the steps to add a new number and update the median using two heaps.

Focus on where to put the new number 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 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