Median of Data Stream Using Two Heaps in DSA Rust - Execution Trace

Concept Flow - Median of Data Stream Using Two Heaps

New number arrives

↓

Compare with max-heap root

↓

Add to max-heap

↓

Balance heaps size

↓

Calculate median

↓

Output median

New numbers go to one of two heaps (max-heap for smaller half, min-heap for larger half). We keep heaps balanced and find median from their roots.

Execution Sample

DSA Rust

max_heap = []
min_heap = []
for num in stream:
    if max_heap.empty() or num <= max_heap.peek():
        max_heap.push(num)
    else:
        min_heap.push(num)
    balance_heaps()
    median = get_median()

Insert numbers into two heaps to keep halves balanced, then get median from heap tops.

Execution Table

Step	Operation	Number Inserted	Max-Heap State	Min-Heap State	Balance Action	Median
1	Insert 5	5	[5]	[]	No balancing needed	5
2	Insert 15	15	[5]	[15]	Heaps balanced (size difference ≤ 1)	10.0
3	Insert 1	1	[5, 1]	[15]	Heaps balanced	5
4	Insert 3	3	[3, 1, 5]	[15]	Moved 5 from max to min heap to balance	4.0
5	Insert 8	8	[3, 1, 5]	[8, 15]	Moved 8 from min to max heap to balance	5
6	Insert 7	7	[7, 3, 1, 5]	[8, 15]	Heaps balanced	6.0
7	Insert 9	9	[7, 3, 1, 5]	[8, 15, 9]	Heaps balanced	7
8	Insert 10	10	[7, 3, 1, 5]	[8, 9, 15, 10]	Moved 7 from max to min heap to balance	8.0
9	Insert 6	6	[6, 5, 1, 3]	[8, 9, 15, 10]	Heaps balanced	7
Exit	Stream ended	-	[6, 5, 1, 3]	[8, 9, 15, 10]	Final balanced heaps	7

💡 All numbers processed; heaps balanced with size difference ≤ 1

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	Final
max_heap	[]	[5]	[5]	[5,1]	[3,1,5]	[3,1,5]	[7,3,1,5]	[7,3,1,5]	[6,5,1,3]	[6,5,1,3]	[6,5,1,3]
min_heap	[]	[]	[15]	[15]	[15]	[8,15]	[8,15]	[8,15,9]	[8,9,15,10]	[8,9,15,10]	[8,9,15,10]
median	-	5	10.0	5	4.0	5	6.0	7	8.0	7	7

Key Moments - 3 Insights

Why do we sometimes move elements between heaps after insertion?

Because we must keep the heaps balanced so their sizes differ by at most 1. This ensures the median can be found easily from the heap tops. See steps 4, 5, and 8 in execution_table where balancing moves happen.

Why do we use a max-heap for smaller half and min-heap for larger half?

Max-heap lets us quickly get the largest of the smaller half, min-heap lets us get the smallest of the larger half. Median is either the top of one heap or average of both. This is shown in the heap states in execution_table.

How is median calculated when heaps have equal size vs when one heap is bigger?

If heaps are equal size, median is average of both tops (see step 2). If one heap is bigger, median is top of that heap (see step 1). This is reflected in the median column.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what balancing action was taken?

A Moved 5 from max-heap to min-heap

B Moved 3 from min-heap to max-heap

C No balancing needed

D Moved 15 from min-heap to max-heap

💡 Hint

Check the 'Balance Action' column at step 4 in execution_table

At which step does the median become 6.0?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Median' column in execution_table for value 6.0

If we insert a number smaller than all current numbers, which heap will it go to initially?

A Min-heap

B Max-heap

C Either heap randomly

D Neither heap

💡 Hint

Refer to the insertion logic in execution_sample and concept_flow

Concept Snapshot

Median of Data Stream Using Two Heaps:
- Use max-heap for smaller half, min-heap for larger half
- Insert new number into correct heap
- Balance heaps so size difference ≤ 1
- Median is top of bigger heap or average of both tops
- Efficient for streaming data median calculation

Full Transcript

This concept uses two heaps to find the median of a stream of numbers efficiently. New numbers are added to either a max-heap (holding smaller half) or a min-heap (holding larger half). After each insertion, heaps are balanced to keep their sizes close. The median is then found by looking at the top elements of the heaps. The execution table shows step-by-step insertion, heap states, balancing actions, and median calculation. Key moments clarify why balancing is needed, why two heaps are used, and how median is computed depending on heap sizes. The visual quiz tests understanding of heap balancing, median values, and insertion logic. This method is efficient and works well for continuous data streams.

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