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()).

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 sort all numbers in ascending order

B. To store all numbers in a single data structure

C. To efficiently keep track of the lower half and upper half of the numbers separately

D. To remove duplicates 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 this helps find the median

   By balancing these heaps, the median is either the top of one heap or the average of tops of both heaps.

3. Final Answer:

   To efficiently keep track of the lower half and upper half of the numbers separately -> Option C

4. Quick Check:

   Two heaps split data halves = efficient median [OK]

Hint: Two heaps split data halves for quick median [OK]

Common Mistakes:

• Thinking heaps sort all numbers fully
• Using one heap only
• Confusing heaps with arrays

2. Which TypeScript syntax correctly declares a max heap using a priority queue for numbers?

easy

A. const maxHeap = new PriorityQueue<number>((a, b) => b - a);

B. const maxHeap = new PriorityQueue<number>((a, b) => a - b);

C. const maxHeap = new PriorityQueue<number>();

D. const maxHeap = new PriorityQueue<number>((a, b) => a + b);

Solution

1. Step 1: Understand max heap comparator

   Max heap comparator returns positive if first is less than second, so b - a creates max heap.

2. Step 2: Check each option

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); uses (b - a) which is correct for max heap; others do not create max heap order.

3. Final Answer:

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); -> Option A

4. Quick Check:

   Comparator b - a = max heap [OK]

Hint: Max heap comparator subtracts first from second [OK]

Common Mistakes:

• Using a - b for max heap (creates min heap)
• Not providing comparator
• Using addition in comparator

3. Given the following sequence of numbers inserted into the data stream: [5, 15, 1, 3], what is the median after all insertions using two heaps?

medium

A. 3

B. 4

C. 5

D. 8

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 -> maxHeap=[5] (top=5), minHeap=[]; Insert 15 -> minHeap=[15] (top=15), sizes 1:1; Insert 1 -> maxHeap=[5,1] (top=5), sizes 2:1; Insert 3 -> maxHeap=[5,3,1] (top=5), sizes 3:1 -> balance (max.size > min.size+1), move max.top=5 to minHeap -> maxHeap=[3,1] (top=3), minHeap=[5,15] (top=5), sizes 2:2.

2. Step 2: Calculate median from heaps

   Sizes equal, median = (maxHeap.top + minHeap.top)/2 = (3 + 5)/2 = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Median of [5,15,1,3] = 4 [OK]

Hint: Median is average of two heap tops if sizes equal [OK]

Common Mistakes:

• Taking median as top of one heap only
• Not balancing heaps after insertion
• Wrong average calculation

4. Consider this TypeScript snippet for adding a number to the data stream median finder:

if (num <= maxHeap.peek()) {
  maxHeap.enqueue(num);
} else {
  minHeap.enqueue(num);
}

// Balance heaps
if (maxHeap.size() > minHeap.size() + 1) {
  minHeap.enqueue(maxHeap.dequeue());
} else if (minHeap.size() > maxHeap.size()) {
  maxHeap.enqueue(minHeap.dequeue());
}

What is the bug in this code?

medium

A. It compares num with minHeap.peek() instead of maxHeap.peek()

B. It balances heaps incorrectly by moving elements the wrong way

C. It uses enqueue instead of push for heaps

D. It does not handle empty maxHeap before peek() call

Solution

1. Step 1: Analyze peek() usage on maxHeap

   If maxHeap is empty, calling peek() causes error because no element exists yet.

2. Step 2: Identify missing empty check

   Code should check if maxHeap is empty before peek() or handle initial insertion separately.

3. Final Answer:

   It does not handle empty maxHeap before peek() call -> Option D

4. Quick Check:

   Empty heap peek() causes runtime error [OK]

Hint: Check heap empty before peek() to avoid errors [OK]

Common Mistakes:

• Assuming heaps always have elements
• Mixing enqueue and push methods
• Balancing heaps incorrectly

5. You want to extend the Median of Data Stream solution to support removing numbers from the stream efficiently. Which data structure modification is best to support both insertion and removal while maintaining median calculation?

hard

A. Use two heaps with a hash map to mark removed elements lazily

B. Use two balanced binary search trees (like AVL or Red-Black trees) instead of heaps

C. Use a single sorted array and binary search for insertion and removal

D. Use two queues to store lower and upper halves

Solution

1. Step 1: Understand removal challenge in heaps

   Heaps do not support efficient arbitrary removal, so direct removal is costly.

2. Step 2: Explain lazy removal with hash map

   Mark elements as removed in a hash map and skip them during heap operations to simulate removal efficiently.

3. Step 3: Compare other options

   Balanced trees support removal but are more complex; arrays are inefficient; queues do not maintain order.

4. Final Answer:

   Use two heaps with a hash map to mark removed elements lazily -> Option A

5. Quick Check:

   Lazy removal with hash map + heaps = efficient median update [OK]

Hint: Lazy removal with hash map keeps heaps efficient [OK]

Common Mistakes:

• Trying direct removal from heaps
• Using arrays causing slow operations
• Ignoring complexity of balanced trees