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.