Median of Data Stream Using Two Heaps in DSA Typescript - 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 quickly find the middle score (median) at any time without sorting all scores every time a new number arrives.

🎯 Goal: Build a program that keeps track of numbers using two heaps (a max heap and a min heap) to efficiently find the median after each new number is added.

📋 What You'll Learn

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

Add numbers to the correct heap to keep the halves balanced or almost balanced.

Calculate the median based on the sizes and top elements of the two heaps.

Print the median after adding each number.

💡 Why This Matters

🌍 Real World

Real-time systems like live scoreboards, stock price monitoring, or sensor data analysis need quick median calculations.

💼 Career

Understanding heaps and median calculation is useful for software engineers working on streaming data, real-time analytics, and performance-critical applications.

1

Create two empty heaps

Create two empty arrays called maxHeap and minHeap to represent the max heap and min heap respectively.

DSA Typescript

const maxHeap: number[] = [];
const minHeap: number[] = [];
// Your code here

Hint

Use two arrays to represent the two heaps. One will store the smaller half of numbers (maxHeap), the other the larger half (minHeap).

2

Add a helper function to insert into heaps

Create a function called addNumber that takes a number num and adds it to either maxHeap or minHeap based on comparison with the top of maxHeap. Use simple array push for now.

DSA Typescript

const maxHeap: number[] = [];
const minHeap: number[] = [];

function addNumber(num: number): void {
    // Your code here
}

Hint

Compare the new number with the first element of maxHeap to decide where to add it.

3

Balance the heaps and find the median

Inside addNumber, after adding num, balance the heaps so their sizes differ by at most 1. Then create a function getMedian that returns the median based on heap sizes and top elements.

DSA Typescript

const maxHeap: number[] = [];
const minHeap: number[] = [];

function addNumber(num: number): void {
    if (maxHeap.length === 0 || num <= maxHeap[0]) {
        maxHeap.push(num);
    } else {
        minHeap.push(num);
    }
    // Your code here to balance heaps
}

function getMedian(): number {
    // Your code here to return median
    return 0;
}

Hint

Balance by moving elements between heaps if one is bigger by more than 1. Median depends on which heap has more elements.

4

Add numbers and print median after each

Add the numbers 5, 15, 1, 3 one by one using addNumber and print the median after each addition using getMedian.

DSA Typescript

const maxHeap: number[] = [];
const minHeap: number[] = [];

function addNumber(num: number): void {
    if (maxHeap.length === 0 || num  minHeap.length + 1) {
        minHeap.push(maxHeap.pop()!);
    } else if (minHeap.length > maxHeap.length) {
        maxHeap.push(minHeap.pop()!);
    }
    maxHeap.sort((a, b) => b - a);
    minHeap.sort((a, b) => a - b);
}

function getMedian(): number {
    if (maxHeap.length > minHeap.length) {
        return maxHeap[0];
    } else {
        return (maxHeap[0] + minHeap[0]) / 2;
    }
}

// Your code here to add numbers and print medians

Hint

Call addNumber with each number and print the median using console.log(getMedian()).