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.