Median of Data Stream Using Two Heaps in DSA Rust - Time & Space Complexity

Time Complexity: Median of Data Stream Using Two Heaps

O(log n)

Understanding Time Complexity

We want to understand how fast we can find the middle value when numbers keep coming in.

How does the time to add numbers and get the middle change as more numbers arrive?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

use std::collections::BinaryHeap;

struct MedianFinder {
    max_heap: BinaryHeap, // lower half
    min_heap: BinaryHeap>, // upper half
}

impl MedianFinder {
    fn add_num(&mut self, num: i32) {
        if self.max_heap.len() == 0 || num <= *self.max_heap.peek().unwrap() {
            self.max_heap.push(num);
        } else {
            self.min_heap.push(std::cmp::Reverse(num));
        }
        // Balance heaps
        if self.max_heap.len() > self.min_heap.len() + 1 {
            if let Some(val) = self.max_heap.pop() {
                self.min_heap.push(std::cmp::Reverse(val));
            }
        } else if self.min_heap.len() > self.max_heap.len() {
            if let Some(std::cmp::Reverse(val)) = self.min_heap.pop() {
                self.max_heap.push(val);
            }
        }
    }

    fn find_median(&self) -> f64 {
        if self.max_heap.len() > self.min_heap.len() {
            *self.max_heap.peek().unwrap() as f64
        } else {
            (*self.max_heap.peek().unwrap() as f64 + self.min_heap.peek().unwrap().0 as f64) / 2.0
        }
    }
}
    

This code keeps two heaps to quickly find the middle number as new numbers come in.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding a number to one of the two heaps and balancing them.
• How many times: Each new number causes one insertion and possibly one removal from a heap.

How Execution Grows With Input

Each new number requires a few heap operations that take time related to the heap size.

Input Size (n)	Approx. Operations
10	About 10 insertions and up to 10 removals, each taking a few steps.
100	About 100 insertions and removals, each a bit longer but still fast.
1000	About 1000 insertions and removals, each taking more steps but still efficient.

Pattern observation: The time per operation grows slowly as the heaps get bigger, not linearly.

Final Time Complexity

Time Complexity: O(log n)

This means adding a number and balancing heaps takes time that grows slowly with the number of elements.

Common Mistake

[X] Wrong: "Adding a number takes constant time because it's just one insert."

[OK] Correct: Inserting into a heap requires rearranging elements to keep order, which takes time growing with heap size.

Interview Connect

Understanding this helps you show how to handle data that changes over time efficiently, a useful skill in many problems.

Self-Check

"What if we used a sorted list instead of heaps? How would the time complexity change?"

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