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.