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

Concept Flow - Median of Data Stream Using Two Heaps

New number arrives

↓

Compare with max-heap top

↓

Add to max-heap

↓

Balance heaps size

↓

Calculate median

↓

Output median

Numbers are split into two heaps: max-heap for smaller half, min-heap for larger half. New numbers go to one heap, then heaps are balanced. Median is top(s) of heaps.

Execution Sample

DSA C

insertNum(5)
insertNum(15)
insertNum(1)
getMedian()

Insert numbers 5, 15, 1 into two heaps and then find the median.

Execution Table

Step	Operation	Max-Heap (Smaller Half)	Min-Heap (Larger Half)	Balance Action	Median	Visual State
1	Insert 5	[5]	[]	No balancing needed	5	Max-Heap: [5], Min-Heap: []
2	Insert 15	[5]	[15]	No balancing needed	(5+15)/2 = 10	Max-Heap: [5], Min-Heap: [15]
3	Insert 1	[5,1]	[15]	Balance: Move 5 from Max to Min	5	Max-Heap: [1], Min-Heap: [5,15]
4	Get Median	[1]	[5,15]	No action	5	Median is top of Min-Heap
5	Insert 3	[3,1]	[5,15]	No balancing needed	4	Max-Heap: [3,1], Min-Heap: [5,15]
6	Get Median	[3,1]	[5,15]	No action	4	Median is average of tops: (3+5)/2=4
7	Insert 8	[5,3,1]	[8,15]	Balance: Move 5 from Max to Min	5	Max-Heap: [3,1], Min-Heap: [5,8,15]
8	Get Median	[3,1]	[5,8,15]	No action	5	Median is top of Min-Heap
9	Insert 7	[5,3,1]	[7,8,15]	No balancing needed	6	Max-Heap: [5,3,1], Min-Heap: [7,8,15]
10	Get Median	[5,3,1]	[7,8,15]	No action	6	Median is average of tops: (5+7)/2=6
11	Insert 9	[7,5,3,1]	[8,9,15]	Balance: Move 7 from Max to Min	7	Max-Heap: [5,3,1], Min-Heap: [7,8,9,15]
12	Get Median	[5,3,1]	[7,8,9,15]	No action	7	Median is top of Min-Heap
13	End	-	-	-	-	No more operations

💡 All numbers inserted and median calculated at each step.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	Final
Max-Heap	[]	[5]	[5]	[1]	[3,1]	[3,1]	[5,3,1]	[5,3,1]	[5,3,1]
Min-Heap	[]	[]	[15]	[5,15]	[5,15]	[5,8,15]	[7,8,15]	[7,8,9,15]	[7,8,9,15]
Median	N/A	5	10	5	4	5	6	7	7

Key Moments - 3 Insights

Why do we use two heaps instead of one to find the median?

Two heaps split the data into smaller and larger halves, making it easy to find the middle value(s). See execution_table steps 1-3 where numbers go to different heaps.

Why do we balance the heaps after insertion?

Balancing keeps the heaps sizes equal or off by one, ensuring median calculation is correct. Look at step 3 where balancing moves an element to keep sizes balanced.

How is the median calculated when heaps have different sizes?

If heaps sizes differ, median is top of the bigger heap. If equal, median is average of both tops. See steps 4 and 6 for examples.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the median?

A 1

B 5

C 10

D 15

💡 Hint

Check the Median column at step 3 in execution_table.

At which step does balancing move an element from max-heap to min-heap?

A Step 9

B Step 7

C Step 3

D Step 11

💡 Hint

Look at Balance Action column in execution_table for step 3.

If we insert a number smaller than all current numbers, where does it go first?

A Max-Heap

B Min-Heap

C Either heap randomly

D Neither heap

💡 Hint

See concept_flow and execution_table steps 1-3 where smaller numbers go to max-heap.

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 sizes (equal or off by one)
- Median is top of max-heap if odd count
- Median is average of tops if even count

Full Transcript

This concept uses two heaps to find the median of a stream of numbers. One heap (max-heap) holds the smaller half of numbers, the other (min-heap) holds the larger half. When a new number arrives, it is compared to the top of the max-heap to decide which heap it belongs to. After insertion, heaps are balanced so their sizes differ by at most one. The median is then either the top of the max-heap (if odd total numbers) or the average of the tops of both heaps (if even total numbers). The execution table shows step-by-step insertion, balancing, and median calculation. Variable tracker shows heap contents and median after each step. Key moments clarify why two heaps are used, why balancing is needed, and how median is calculated. Visual quiz questions test understanding of median values and heap operations at specific steps.

Practice

1. What is the main purpose of using two heaps (a max-heap and a min-heap) to find the median of a data stream?

easy

A. To store all numbers in a single data structure

B. To sort all numbers in ascending order

C. To remove duplicate numbers from the stream

D. To efficiently keep track of the lower half and upper half of the numbers separately

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

   By balancing these heaps, the median is either the top of one heap or the average of the tops of both heaps.

3. Final Answer:

   To efficiently keep track of the lower half and upper half of the numbers separately -> Option D

4. Quick Check:

   Two heaps split data halves = To efficiently keep track of the lower half and upper half of the numbers separately [OK]

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

Common Mistakes:

• Thinking heaps sort all data fully
• Using one heap only
• Confusing heaps with arrays

2. Which of the following is the correct way to insert a new number into the two heaps when maintaining the median?

easy

A. Insert into the heap based on comparison with max-heap top

B. Insert into min-heap only

C. Insert into max-heap only

D. Always insert into min-heap first, then balance heaps

Solution

1. Step 1: Decide where to insert the new number

   If the new number is less than or equal to the max-heap top, insert into max-heap; otherwise, insert into min-heap.

2. Step 2: Balance the heaps if needed

   After insertion, balance the heaps so their sizes differ by at most one.

3. Final Answer:

   Insert into the heap based on comparison with max-heap top -> Option A

4. Quick Check:

   Compare with max-heap top to choose heap [OK]

Hint: Compare new number with max-heap top to choose heap [OK]

Common Mistakes:

• Always inserting into one heap without condition
• Not balancing heaps after insertion
• Inserting into wrong heap based on min-heap top

3. Consider the following sequence of numbers inserted into the data stream: 5, 15, 1, 3. What is the median after all insertions using two heaps?

Insert 5
Insert 15
Insert 1
Insert 3
Find median

medium

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 into max-heap ([5]); insert 15 into min-heap ([15]); insert 1 (<=5) into max-heap ([5,1] top=5); insert 3 (<=5) into max-heap ([5,3,1] top=5), sizes 3 vs 1, balance: min.push(5) ([15,5] top=5), max.pop() ([3,1] top=3).

2. Step 2: Calculate median from heaps

   Heaps sizes equal (2 and 2), median = average of max-heap top (3) and min-heap top (5) = (3+5)/2 = 4.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Median of [1,3,5,15] = 4 [OK]

Hint: Median is average when heaps equal size [OK]

Common Mistakes:

• Taking median as max-heap top only
• Not balancing heaps after insertions
• Calculating median incorrectly as 5 or 3

4. The following code snippet tries to maintain median using two heaps but has a bug. What is the bug?

void addNumber(int num, priority_queue<int>& maxHeap, priority_queue& minHeap) {
    if (maxHeap.empty() || num <= maxHeap.top()) {
        maxHeap.push(num);
    } else {
        minHeap.push(num);
    }
    if (maxHeap.size() > minHeap.size() + 1) {
        minHeap.push(maxHeap.top());
        maxHeap.pop();
    } else if (minHeap.size() > maxHeap.size() + 1) {
        maxHeap.push(minHeap.top());
        minHeap.pop();
    }
}

medium

A. The balancing pops top element before pushing, causing wrong order

B. The condition to insert into maxHeap is incorrect

C. The heaps are not balanced after insertion

D. The function does not return the median

Solution

1. Step 1: Analyze balancing logic

   When balancing, the code pops the top element of one heap before pushing the new top to the other, which moves the wrong element.

2. Step 2: Explain correct balancing

   Correct approach is to push heap.top() first, then pop() to transfer the correct top element.

3. Final Answer:

   The balancing pops top element before pushing, causing wrong order -> Option A

4. Quick Check:

   Push top before pop to balance heaps correctly [OK]

Hint: Push top before pop when balancing heaps [OK]

Common Mistakes:

• Popping before pushing the correct top
• Ignoring heap size difference conditions
• Not handling empty heaps properly

5. You have a data stream of integers and want to find the median after each insertion. Using two heaps, how would you handle the case when the total number of elements is odd?

hard

A. The median is always the top of the min-heap

B. The median is the top element of the heap with one extra element

C. The median is always the top of the max-heap

D. The median is the average of the tops of both heaps

Solution

1. Step 1: Understand heap size difference

   When total elements are odd, one heap will have one more element than the other.

2. Step 2: Determine median from heaps

   The median is the top element of the heap that has the extra element, because it holds the middle value.

3. Final Answer:

   The median is the top element of the heap with one extra element -> Option B

4. Quick Check:

   Odd count median = top of larger heap [OK]

Hint: Median is top of bigger heap when odd count [OK]

Common Mistakes:

• Averaging tops when count is odd
• Assuming max-heap always has extra element
• Ignoring heap size difference