Median of Data Stream Using Two Heaps in DSA C++ - Build from Scratch

Median of Data Stream Using Two Heaps

📖 Scenario: Imagine you are building a system that receives numbers one by one, like scores from a game played live. You want to find the middle score (median) at any time quickly.

🎯 Goal: Build a program that keeps track of the median of numbers as they come in, using two heaps (priority queues) to organize the data efficiently.

📋 What You'll Learn

Use two heaps: a max-heap for the lower half of numbers and a min-heap for the upper half.

Balance the heaps so their sizes differ by at most one.

Insert numbers one by one and update the median after each insertion.

Print the median after all insertions.

💡 Why This Matters

🌍 Real World

Finding the median in real-time data streams like live sensor data, stock prices, or game scores.

💼 Career

Useful for roles in data engineering, real-time analytics, and software development involving streaming data.

1

Create two heaps for storing numbers

Create a max-heap called lower and a min-heap called higher using priority_queue in C++.

DSA C++

# Create two heaps: max-heap 'lower' and min-heap 'higher'
// Your code here

Hint

Use std::priority_queue<int> for max-heap and std::priority_queue<int, std::vector<int>, std::greater<int>> for min-heap.

2

Add a vector of numbers and a function to insert numbers

Create a vector called numbers with these values: {5, 15, 1, 3}. Then write a function called addNumber that takes an int num and inserts it into the correct heap (lower or higher) based on its value.

DSA C++

#include 
#include 
#include 

std::priority_queue lower; // max-heap
std::priority_queue, std::greater> higher; // min-heap

std::vector numbers = {5, 15, 1, 3};

void addNumber(int num) {
    // Your code here
}

int main() {
    return 0;
}

Hint

Insert num into lower if it is smaller or equal to the max of lower, else into higher.

3

Balance the heaps and process all numbers

Write a function called balanceHeaps that keeps the size difference between lower and higher at most 1 by moving elements between them. Then, in main, use a for loop to add each number from numbers using addNumber, call balanceHeaps after each insertion.

DSA C++

#include 
#include 
#include 

std::priority_queue lower; // max-heap
std::priority_queue, std::greater> higher; // min-heap

std::vector numbers = {5, 15, 1, 3};

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

void balanceHeaps() {
    // Your code here
}

int main() {
    for (int num : numbers) {
        addNumber(num);
        balanceHeaps();
    }
    return 0;
}

Hint

Move the top element from the bigger heap to the smaller heap if size difference is more than 1.

4

Calculate and print the median after all insertions

Write a function called getMedian that returns a double median based on the sizes of lower and higher. Then, in main, after processing all numbers, print the median using std::cout.

DSA C++

#include 
#include 
#include 

std::priority_queue lower; // max-heap
std::priority_queue, std::greater> higher; // min-heap

std::vector numbers = {5, 15, 1, 3};

void addNumber(int num) {
    if (lower.empty() || num  higher.size() + 1) {
        higher.push(lower.top());
        lower.pop();
    } else if (higher.size() > lower.size() + 1) {
        lower.push(higher.top());
        higher.pop();
    }
}

double getMedian() {
    // Your code here
}

int main() {
    for (int num : numbers) {
        addNumber(num);
        balanceHeaps();
    }
    std::cout << getMedian() << std::endl;
    return 0;
}

Hint

If both heaps have the same size, median is average of their tops. Otherwise, median is top of the bigger heap.

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