Median of Data Stream Using Two Heaps in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a max heap using Rust's BinaryHeap.

DSA Rust

let mut max_heap = std::collections::BinaryHeap::new();
max_heap.[1](10);

Drag options to blanks, or click blank then click option'

Apush

Bpop

Cpeek

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push

Using peek which only views the top element

The push method adds an element to the heap.

2fill in blank

medium

Complete the code to get the smallest element from a min heap simulated by a max heap in Rust.

DSA Rust

let mut min_heap = std::collections::BinaryHeap::new();
min_heap.push(-5);
min_heap.push(-10);
let smallest = -min_heap.[1]().unwrap();

Drag options to blanks, or click blank then click option'

Apush

Bpeek

Cremove

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek which does not remove the element

Using push which adds elements

pop removes and returns the top element, which is the smallest when values are negated.

3fill in blank

hard

Fix the error in balancing the two heaps by moving the top element from max_heap to min_heap.

DSA Rust

if max_heap.len() > min_heap.len() + 1 {
    let val = max_heap.[1]().unwrap();
    min_heap.push(-val);
}

Drag options to blanks, or click blank then click option'

Apop

Bpeek

Cpush

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek which does not remove the element

Using push which adds elements

pop removes the top element so it can be moved to the other heap.

4fill in blank

hard

Fill both blanks to calculate the median when heaps have equal size.

DSA Rust

if max_heap.len() == min_heap.len() {
    median = (max_heap.[1]().unwrap() + (-min_heap.[2]().unwrap())) as f64 / 2.0;
}

Drag options to blanks, or click blank then click option'

Apeek

Bpop

Clen

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop which removes elements

Using len which returns size, not element

peek returns the top element without removing it, needed to calculate median.

5fill in blank

hard

Fill all three blanks to insert a new number and balance the heaps correctly.

DSA Rust

if max_heap.len() == 0 || num <= max_heap.[1]().unwrap() {
    max_heap.[2](num);
} else {
    min_heap.[3](-num);
}

Drag options to blanks, or click blank then click option'

Apeek

Bpush

Cpop

Dlen

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push

Using len instead of peek for comparison

peek checks the top element, push adds the new number to the correct heap.

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