Median of Data Stream Using Two Heaps in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using two heaps to find the median of a data stream?

Use a max heap to store the smaller half of numbers and a min heap to store the larger half. This way, the median is either the top of one heap or the average of the tops of both heaps.

beginner

Why do we balance the sizes of the two heaps when finding the median?

Balancing ensures the heaps differ in size by at most one, so the median can be found easily from the top elements of the heaps.

beginner

In the two heaps approach, which heap stores the smaller half of the numbers?

The max heap stores the smaller half, so its top is the largest of the smaller numbers.

beginner

How do you find the median when the total number of elements is even using two heaps?

Take the average of the top elements of both heaps (max heap top + min heap top) divided by 2.

intermediate

What Rust data structure can be used to implement a max heap since Rust's BinaryHeap is a max heap by default?

Rust's std::collections::BinaryHeap is a max heap by default. To implement a min heap, you can store the negative of numbers or use the Reverse wrapper.

Which heap stores the larger half of the numbers in the two heaps approach?

A Max heap

B Both heaps store the same numbers

C Min heap

D Neither heap stores the larger half

The min heap stores the larger half of the numbers so its top is the smallest of the larger numbers.

What is the maximum allowed size difference between the two heaps?

A No limit

B 0

C 2

D 1

The heaps are balanced so their sizes differ by at most one to easily find the median.

If the total number of elements is odd, where is the median found?

A Top of the heap with more elements

B Top of min heap

C Average of both heaps' tops

D Top of max heap

The median is the top of the heap that has one extra element when the total count is odd.

In Rust, how can you implement a min heap using BinaryHeap?

A Use BinaryHeap as is

B Store negative values or use Reverse wrapper

C Use a Vec and sort it every time

D Use a linked list

Rust's BinaryHeap is max heap by default; to get min heap behavior, store negative values or use std::cmp::Reverse.

Why do we use two heaps instead of sorting all elements every time?

A Two heaps allow efficient insertion and median retrieval

B Sorting is faster

C Heaps use less memory

D Heaps are easier to implement

Two heaps allow adding numbers and finding median in O(log n) time, better than sorting every time.

Explain how two heaps help find the median in a data stream.

Think about splitting numbers into two groups and how their tops relate to the median.

Describe how to maintain the balance of two heaps when adding a new number.

Consider where the new number fits and how to keep heaps balanced.

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