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?

↓

Push to max-heap

↓

Balance heaps size difference <=1

↓

Calculate median

↓

Output median

New numbers go into one of two heaps (max-heap for smaller half, min-heap for larger half). We keep heaps balanced, then median is top of one or average of both.

Execution Sample

DSA C++

maxHeap = empty
minHeap = empty
addNum(num):
  if maxHeap empty or num <= maxHeap.top(): push to maxHeap
  else push to minHeap
  balance heaps
getMedian():
  if sizes equal: return avg tops
  else return top of bigger heap

Add numbers to two heaps to keep halves balanced, then median is top(s) of heaps.

Execution Table

Step	Operation	Number Added	Max-Heap State	Min-Heap State	Balance Action	Median
1	Add number	10	[10]	[]	No balancing needed	10
2	Add number	20	[10]	[20]	No balancing needed	15
3	Add number	30	[10, 20]	[30]	Move 20 from minHeap to maxHeap	20
4	Add number	5	[10, 5]	[20, 30]	Move 20 from maxHeap to minHeap	15
5	Add number	25	[10, 5]	[20, 25, 30]	No balancing needed	20
6	Add number	2	[10, 5, 2]	[20, 25, 30]	No balancing needed	15
7	Add number	8	[10, 8, 2, 5]	[20, 25, 30]	No balancing needed	10
Exit	Stream ended	-	[10, 8, 2, 5]	[20, 25, 30]	Balanced heaps	10

💡 All numbers added and heaps balanced with size difference <=1

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
maxHeap (as max-heap array)	[]	[10]	[10]	[10, 20]	[10, 5]	[10, 5]	[10, 5, 2]	[10, 8, 2, 5]	[10, 8, 2, 5]
minHeap (as min-heap array)	[]	[]	[20]	[30]	[20, 30]	[20, 25, 30]	[20, 25, 30]	[20, 25, 30]	[20, 25, 30]
Median	-	10	15	20	15	20	15	10	10

Key Moments - 3 Insights

Why do we move elements between heaps after insertion?

Because heaps must be balanced so their sizes differ by at most 1, as shown in steps 3 and 4 in execution_table where balancing moves elements to maintain this.

Why do we compare the new number with maxHeap top to decide where to insert?

Because maxHeap holds the smaller half, so if number is smaller or equal to maxHeap top, it belongs there; else it goes to minHeap. This is shown in step 1 and 2.

How is median calculated when heaps have equal size?

Median is average of maxHeap top and minHeap top, as in step 2 where median is (10+20)/2=15.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what balancing action is performed?

A Move 20 from minHeap to maxHeap

B Move 10 from maxHeap to minHeap

C No balancing needed

D Swap tops of both heaps

💡 Hint

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

At which step does the median become 15?

A Step 1

B Step 2

C Step 4

D Step 6

💡 Hint

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

If we add a number smaller than maxHeap top, where does it go?

A Into minHeap

B Into maxHeap

C Removed immediately

D Into both heaps

💡 Hint

Refer to the 'Operation' and 'Number Added' logic in execution_sample and key_moments

Concept Snapshot

Median of Data Stream Using Two Heaps:
- Use max-heap for smaller half, min-heap for larger half
- Insert new number into appropriate 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. One heap (max-heap) stores the smaller half of numbers, the other (min-heap) stores the larger half. When a new number arrives, it is compared to the top of the max-heap to decide where to insert. After insertion, heaps are balanced so their sizes differ by at most one. The median is then either the top of the larger heap or the average of both tops if heaps are equal in size. The execution table shows step-by-step how numbers are added, heaps updated, balanced, and median calculated. Variable tracker shows heap contents after each step. Key moments clarify why balancing is needed and how median is computed. Visual quiz questions test understanding of these steps.

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 efficiently find the median by balancing smaller and larger halves of the data

B. To sort the entire data stream in ascending order

C. To store all elements in one heap for quick access

D. To remove duplicate elements from the data stream

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 median is found

   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 A

4. Quick Check:

   Two heaps balance halves = median found fast [OK]

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

Common Mistakes:

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

2. Which of the following is the default way to declare a max-heap in C++ using the priority_queue?

easy

A. priority_queue maxHeap;

B. priority_queue<int> maxHeap;

C. priority_queue maxHeap;

D. priority_queue maxHeap;

Solution

1. Step 1: Recall default priority_queue behavior

   By default, priority_queue in C++ is a max-heap using less<int>.

2. Step 2: Identify correct declaration

   Declaring priority_queue<int> maxHeap; creates a max-heap without extra parameters.

3. Final Answer:

   priority_queue<int> maxHeap; -> Option B

4. Quick Check:

   Default priority_queue = max-heap [OK]

Hint: Default priority_queue is max-heap [OK]

Common Mistakes:

• Using greater<int> for max-heap
• Omitting vector container
• Confusing max-heap with min-heap syntax

3. Consider the following C++ code snippet that inserts numbers into two heaps to find the median:

priority_queue<int> maxHeap;
priority_queue minHeap;

// Insert 10
maxHeap.push(10);
// Insert 20
minHeap.push(20);
// Insert 15
if (15 <= maxHeap.top()) maxHeap.push(15); else minHeap.push(15);

// Balance heaps
if (maxHeap.size() > minHeap.size() + 1) {
  minHeap.push(maxHeap.top());
  maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
  maxHeap.push(minHeap.top());
  minHeap.pop();
}

// Calculate median
if (maxHeap.size() == minHeap.size())
  cout << (maxHeap.top() + minHeap.top()) / 2.0 << endl;
else
  cout << maxHeap.top() << endl;

What is the output of this code?

medium

A. 15

B. 15.0

C. 12.5

D. 20

Solution

1. Step 1: Insert elements and balance heaps

   Insert 10 into maxHeap: maxHeap = [10]. Insert 20 into minHeap: minHeap = [20]. Insert 15: 15 > 10, so goes to minHeap: minHeap = [15, 20]. Balance heaps: minHeap size (2) > maxHeap size (1), so move minHeap top (15) to maxHeap. Now maxHeap = [15, 10], minHeap = [20].

2. Step 2: Calculate median

   maxHeap size = 2, minHeap size = 1, so median is maxHeap.top() = 15. Sizes unequal, cout << maxHeap.top() << endl; outputs 15.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Median after balancing = 15 [OK]

Hint: Balance heaps, median = top of larger heap or average [OK]

Common Mistakes:

• Not balancing heaps correctly
• Integer division instead of float
• Wrong heap insertion condition

4. The following code snippet is intended to maintain two heaps for median calculation. Identify the bug:

priority_queue<int> maxHeap;
priority_queue minHeap;

void addNumber(int num) {
  if (maxHeap.empty() || num <= maxHeap.top()) {
    maxHeap.push(num);
  } else {
    minHeap.push(num);
  }

  if (maxHeap.size() > minHeap.size()) {
    minHeap.push(maxHeap.top());
    maxHeap.pop();
  } else if (minHeap.size() > maxHeap.size() + 1) {
    maxHeap.push(minHeap.top());
    minHeap.pop();
  }
}

medium

A. The heaps are not declared correctly for median calculation

B. The comparison operator in if condition should be num >= maxHeap.top()

C. The balancing condition for maxHeap is incorrect; it should check if maxHeap.size() > minHeap.size() + 1

D. The function does not insert elements into any heap

Solution

1. Step 1: Analyze balancing conditions

   The code moves element from maxHeap to minHeap if maxHeap.size() > minHeap.size(), but it should only do so if maxHeap.size() > minHeap.size() + 1 to keep heaps balanced properly.

2. Step 2: Confirm correct balancing logic

   Proper balancing ensures size difference is at most 1. The current condition causes unnecessary moves, breaking balance.

3. Final Answer:

   The balancing condition for maxHeap is incorrect; it should check if maxHeap.size() > minHeap.size() + 1 -> Option C

4. Quick Check:

   Balance heaps only if size difference > 1 [OK]

Hint: Balance heaps only if size difference > 1 [OK]

Common Mistakes:

• Wrong balancing condition
• Swapping heap roles
• Incorrect comparison operators

5. You are given a stream of integers: [5, 15, 1, 3, 8, 7, 9, 10, 6, 11]. Using two heaps to find the median after each insertion, what is the median after inserting all elements?

hard

A. 8

B. 7

C. 6.5

D. 7.5

Solution

1. Step 1: Insert elements and balance heaps step-by-step

   After processing the entire stream with proper insertion (to maxHeap if <= max.top or empty, else minHeap) and balancing (rebalance if max.size > min.size + 1 or min.size > max.size), final state: maxHeap size=5 (top=7), minHeap size=5 (top=8).

2. Step 2: Calculate final median

   After all insertions, maxHeap size = 5, minHeap size = 5, median = average of tops: (7 + 8) / 2 = 7.5

3. Final Answer:

   7.5 -> Option D

4. Quick Check:

   Median after all insertions = 7.5 [OK]

Hint: Median = average of two heap tops if equal size [OK]

Common Mistakes:

• Not balancing heaps after each insertion
• Calculating median from wrong heap
• Forgetting to average when heaps equal size