Median of Data Stream Using Two Heaps in DSA Rust - 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 by many users. You want to quickly find the middle score (median) at any time without sorting all numbers every time a new score arrives.

🎯 Goal: Build a program that keeps track of the median of a stream of numbers using two heaps (a max heap and a min heap). You will add numbers one by one and then find the median efficiently.

📋 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 them balanced in size.

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

Print the median after adding all numbers.

💡 Why This Matters

🌍 Real World

This technique is used in real-time data analysis where you need to find the middle value quickly, such as live score tracking, financial data streams, or sensor data monitoring.

💼 Career

Understanding how to maintain running medians efficiently is useful for software engineers working on streaming data, real-time analytics, and performance-critical applications.

1

Create two empty heaps

Create two empty heaps: a max heap called low and a min heap called high using BinaryHeap from Rust's standard library. Use std::collections::BinaryHeap for both. For the min heap, store numbers as negative values in a max heap to simulate a min heap.

DSA Rust

// Create two empty heaps: low (max heap) and high (min heap simulated)
// Your code here

Hint

Use BinaryHeap::new() to create empty heaps. Remember, Rust's BinaryHeap is a max heap by default.

2

Add a helper function to add numbers to heaps

Add a function called add_number that takes a number num: i32, and mutable references to low and high heaps. Inside, add num to low if it is empty or num is less than or equal to the top of low. Otherwise, add num to high as negative to simulate min heap. Then balance the heaps so their sizes differ by at most 1.

DSA Rust

use std::collections::BinaryHeap;

fn main() {
    let mut low: BinaryHeap = BinaryHeap::new();
    let mut high: BinaryHeap = BinaryHeap::new();
}

// Add function add_number(num: i32, low: &mut BinaryHeap, high: &mut BinaryHeap)
// Your code here

Hint

Check if low is empty or num is less or equal to low.peek() to decide where to add. Use pop() and push() to balance heaps.

3

Add a function to find the median

Add a function called find_median that takes references to low and high heaps and returns a f64 median. If heaps have equal size, return the average of the top of low and negative top of high. If low has more elements, return its top as f64.

DSA Rust

use std::collections::BinaryHeap;

fn add_number(num: i32, low: &mut BinaryHeap, high: &mut BinaryHeap) {
    if low.peek().map_or(true, |&x| num  high.len() + 1 {
        if let Some(top) = low.pop() {
            high.push(-top);
        }
    } else if high.len() > low.len() {
        if let Some(top) = high.pop() {
            low.push(-top);
        }
    }
}

// Add function find_median(low: &BinaryHeap, high: &BinaryHeap) -> f64
// Your code here

fn main() {
    let mut low: BinaryHeap = BinaryHeap::new();
    let mut high: BinaryHeap = BinaryHeap::new();
}

Hint

Use peek() to get the top elements. Return average if sizes equal, else return top of low.

4

Add numbers and print the median

In main, add these numbers in order: 5, 15, 1, 3 using add_number. Then print the median using find_median with println!("{:.1}", median) to show one decimal place.

DSA Rust

use std::collections::BinaryHeap;

fn add_number(num: i32, low: &mut BinaryHeap, high: &mut BinaryHeap) {
    if low.peek().map_or(true, |&x| num  high.len() + 1 {
        if let Some(top) = low.pop() {
            high.push(-top);
        }
    } else if high.len() > low.len() {
        if let Some(top) = high.pop() {
            low.push(-top);
        }
    }
}

fn find_median(low: &BinaryHeap, high: &BinaryHeap) -> f64 {
    if low.len() == high.len() {
        let low_top = *low.peek().unwrap() as f64;
        let high_top = -*high.peek().unwrap() as f64;
        (low_top + high_top) / 2.0
    } else {
        *low.peek().unwrap() as f64
    }
}

fn main() {
    let mut low: BinaryHeap = BinaryHeap::new();
    let mut high: BinaryHeap = BinaryHeap::new();

    // Add numbers 5, 15, 1, 3 using add_number
    // Print the median with one decimal place
    // Your code here
}

Hint

Call add_number for each number. Then call find_median and print with println!("{:.1}", median).

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 the entire data stream before finding the median

B. To store all elements in one heap and ignore the other

C. To efficiently find the median by balancing smaller and larger halves of the data

D. To use heaps only for insertion speed without median calculation

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: How this helps find the median

   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 C

4. Quick Check:

   Two heaps balance halves = median found fast [OK]

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

Common Mistakes:

• Thinking heaps sort all data fully
• Using only one heap for median
• Ignoring balancing heaps after insertion

2. Which Rust data structure is best suited to implement a max-heap for the Median of Data Stream problem?

easy

A. BinaryHeap (max-heap by default)

B. HashMap storing counts of elements

C. Vec with manual sorting after each insertion

D. LinkedList for fast insertion and removal

Solution

1. Step 1: Identify Rust's heap implementation

   Rust's standard library provides BinaryHeap which is a max-heap by default.

2. Step 2: Using Reverse wrapper for min-heap

   To create a min-heap, BinaryHeap with Reverse wrapper is used; for max-heap, BinaryHeap alone suffices.

3. Final Answer:

   BinaryHeap (max-heap by default) -> Option A

4. Quick Check:

   BinaryHeap = max-heap in Rust [OK]

Hint: Rust BinaryHeap is max-heap by default [OK]

Common Mistakes:

• Using Vec and sorting every time (slow)
• Confusing HashMap with heap
• Using LinkedList which is not a heap

3. What will be the median after inserting the numbers 5, 15, 1, 3 in order using two heaps?

medium

A. 6

B. 5

C. 3

D. 4

Solution

1. Step 1: Insert 5 and find median

   Max-heap: [5], Min-heap: [], median = 5

2. Step 2: Insert 15 and balance heaps

   Max-heap: [5], Min-heap: [15], median = (5+15)/2 = 10

3. Step 3: Insert 1 and rebalance

   Max-heap: [5,1], Min-heap: [15], median = 5

4. Step 4: Insert 3 and rebalance

   Max-heap: [3,1], Min-heap: [5,15], median = (3+5)/2 = 4

5. Final Answer:

   4 -> Option D

6. Quick Check:

   Median after 4 inserts = 4 [OK]

Hint: Balance heaps after each insert, median is middle value(s) [OK]

Common Mistakes:

• Not balancing heaps after insertion
• Taking median as last inserted number
• Incorrect average calculation for even count

4. Given this Rust snippet for adding a number to heaps, what is the bug?

if num <= *max_heap.peek().unwrap() {
    max_heap.push(num);
} else {
    min_heap.push(num);
}

if max_heap.len() > min_heap.len() + 1 {
    let val = max_heap.pop().unwrap();
    min_heap.push(val);
} else if min_heap.len() > max_heap.len() {
    let val = min_heap.pop().unwrap();
    max_heap.push(val);
}

medium

A. Missing check for empty max_heap before peek() causing panic

B. Heaps are not balanced after insertion

C. Should pop from min_heap when max_heap is larger

D. No bug, code balances heaps correctly

Solution

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

   Calling peek() on an empty max_heap causes unwrap() panic because there is no element.

2. Step 2: Identify missing empty check

   Code should check if max_heap is empty before peek() to avoid runtime error.

3. Final Answer:

   Missing check for empty max_heap before peek() causing panic -> Option A

4. Quick Check:

   peek() on empty heap = panic without check [OK]

Hint: Always check heap is not empty before peek() [OK]

Common Mistakes:

• Assuming heaps always have elements before peek()
• Confusing which heap to pop from when balancing
• Ignoring unwrap() panic possibility

5. How would you modify the two heaps approach to efficiently find the median if the data stream can contain duplicate numbers and you want to remove numbers as well?

hard

A. Use only one heap and sort after every insertion and removal

B. Use two heaps plus a hash map to track counts and lazy removal of elements

C. Use a balanced binary search tree instead of heaps

D. Ignore duplicates and only keep unique numbers in heaps

Solution

1. Step 1: Understand problem with duplicates and removals

   Heaps alone cannot remove arbitrary elements efficiently, especially duplicates.

2. Step 2: Use hash map for counts and lazy removal

   Track counts of elements in a hash map and mark elements for removal without immediate heap deletion.

3. Step 3: Clean heaps lazily during median calculation

   Remove invalid elements from heap tops lazily to maintain correct median.

4. Final Answer:

   Use two heaps plus a hash map to track counts and lazy removal of elements -> Option B

5. Quick Check:

   Heaps + hash map = efficient median with removals [OK]

Hint: Combine heaps with hash map for removals and duplicates [OK]

Common Mistakes:

• Trying to remove elements directly from heaps
• Ignoring duplicates in median calculation
• Using only sorting which is inefficient