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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Median after inserting numbers

What is the median after inserting the following numbers in order: 5, 15, 1, 3 using the two heaps approach?

DSA C++

class MedianFinder {
private:
    std::priority_queue<int> maxHeap; // lower half
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // upper half

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

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

    double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        } else {
            return maxHeap.top();
        }
    }
};

MedianFinder mf;
mf.addNum(5);
mf.addNum(15);
mf.addNum(1);
mf.addNum(3);
return mf.findMedian();

A 3.0

B 4.0

C 5.0

D 6.0

💡 Hint

Remember to balance the two heaps after each insertion and then find the median based on their sizes.

After inserting 5, 15, 1, 3, the two heaps hold [3,1] in maxHeap and [5,15] in minHeap. The median is the average of the two middle values (3 and 5), which is 4.0.

🧠 Conceptual

intermediate

Why use two heaps for median?

Why do we use two heaps (a max heap and a min heap) to find the median in a data stream?

A To store all numbers in max heap and min heap separately for backup

B To sort all numbers in ascending order using two heaps

C To keep the smaller half of numbers in max heap and larger half in min heap for quick median calculation

D To use heaps for faster insertion only, median is calculated by sorting later

💡 Hint

Think about how median relates to the middle values of sorted data.

Two heaps split the data into lower half (max heap) and upper half (min heap). This allows quick access to middle values needed for median calculation without sorting all data.

🔧 Debug

advanced

Identify the bug in heap balancing

What is the bug in the following code snippet for balancing heaps after insertion?

DSA C++

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

A The conditions for balancing are reversed; maxHeap should allow one extra element, not minHeap

B The pop operations are missing after pushing elements

C The code does not check for empty heaps before accessing top()

D The code balances heaps correctly, no bug

💡 Hint

Check which heap should have the extra element when sizes differ by one.

The max heap (lower half) should be allowed to have one more element than the min heap. The conditions are reversed here, causing incorrect balancing.

❓ Predict Output

advanced

Median after multiple insertions

What is the median after inserting these numbers in order: 2, 4, 7, 1, 5, 3 using the two heaps approach?

DSA C++

MedianFinder mf;
mf.addNum(2);
mf.addNum(4);
mf.addNum(7);
mf.addNum(1);
mf.addNum(5);
mf.addNum(3);
return mf.findMedian();

A 3.5

B 4.0

C 3.0

D 4.5

💡 Hint

Balance heaps after each insertion and find the middle two numbers for even count.

After all insertions, the two middle numbers are 3 and 4, so median is (3 + 4) / 2 = 3.5.

🧠 Conceptual

expert

Time complexity of median finding with two heaps

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

A Adding a number: O(log n), Finding median: O(log n)

B Adding a number: O(n), Finding median: O(log n)

C Adding a number: O(1), Finding median: O(n)

D Adding a number: O(log n), Finding median: O(1)

💡 Hint

Consider heap insertion and top element access times.

Insertion into a heap is O(log n). Finding median is O(1) because it involves accessing the top elements of 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 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