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

Concept Flow - Median of Data Stream Using Two Heaps

Start

↓

New number arrives

↓

Compare with max-heap root

↓

Insert into max-heap

↓

Insert into min-heap

↓

Balance heaps sizes

↓

Calculate median

↓

Output median

↓

Wait for next number

New numbers go into one of two heaps (max-heap for smaller half, min-heap for larger half). Heaps are balanced to keep sizes close. Median is from roots of heaps.

Execution Sample

DSA Go

maxHeap = []
minHeap = []
AddNum(num):
  if maxHeap empty or num <= maxHeap[0]:
    push maxHeap num
  else:
    push minHeap num
  balance heaps
  median = compute median

Add numbers to two heaps, balance them, then find median from heap tops.

Execution Table

Step	Operation	Number Added	Max-Heap Nodes	Min-Heap Nodes	Balance Action	Median	Visual State
1	Add number	5	[5]	[]	No balance needed	5	Max-Heap: 5 Min-Heap:
2	Add number	2	[5, 2]	[]	Balance: move maxHeap root to minHeap	3.5	Max-Heap: 2 Min-Heap: 5
3	Add number	10	[2]	[5, 10]	Balance: move minHeap root to maxHeap	5	Max-Heap: 5, 2 Min-Heap: 10
4	Add number	1	[5, 2, 1]	[10]	No balance needed	3.5	Max-Heap: 5, 2, 1 Min-Heap: 10
5	Add number	3	[5, 3, 1, 2]	[10]	Balance: move maxHeap root to minHeap	5	Max-Heap: 3, 2, 1 Min-Heap: 5, 10
6	Add number	8	[3, 2, 1]	[5, 10, 8]	Balance: move minHeap root to maxHeap	5.5	Max-Heap: 5, 3, 1, 2 Min-Heap: 8, 10
7	Add number	7	[5, 3, 1, 2]	[7, 10, 8]	No balance needed	5.5	Max-Heap: 5, 3, 1, 2 Min-Heap: 7, 10, 8
8	Add number	6	[5, 3, 1, 2, 6]	[7, 10, 8]	Balance: move maxHeap root to minHeap	6	Max-Heap: 6, 5, 1, 2, 3 Min-Heap: 7, 10, 8
9	Add number	4	[6, 5, 1, 2, 3]	[4, 7, 8, 10]	Balance: move minHeap root to maxHeap	5.5	Max-Heap: 6, 5, 4, 2, 3, 1 Min-Heap: 7, 10, 8
10	Add number	9	[6, 5, 4, 2, 3, 1]	[7, 9, 8, 10]	No balance needed	6	Max-Heap: 6, 5, 4, 2, 3, 1 Min-Heap: 7, 9, 8, 10
11	Termination	-	[6, 5, 4, 2, 3, 1]	[7, 9, 8, 10]	Heaps balanced within 1 size difference	6	Final median after all insertions

💡 All numbers processed; heaps balanced; median computed from heap tops.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
maxHeap	[]	[5]	[2]	[5, 2]	[5, 2, 1]	[3, 2, 1]	[5, 3, 1, 2]	[5, 3, 1, 2]	[6, 5, 1, 2, 3]	[6, 5, 4, 2, 3, 1]	[6, 5, 4, 2, 3, 1]	[6, 5, 4, 2, 3, 1]
minHeap	[]	[]	[5]	[5, 10]	[10]	[5, 10]	[8, 10]	[7, 10, 8]	[7, 10, 8]	[4, 7, 8, 10]	[7, 9, 8, 10]	[7, 9, 8, 10]
median	-	5	3.5	5	3.5	5	5.5	5.5	6	5.5	6	6

Key Moments - 3 Insights

Why do we move the root element from one heap to another during balancing?

Because heaps must have sizes differing by at most 1 to correctly find the median. Moving the root (smallest or largest) keeps the halves balanced, as shown in steps 2, 3, 5, 6, and 9 in the execution_table.

Why do we compare the new number with the max-heap root to decide where to insert?

The max-heap root holds the largest number in the smaller half. If the new number is smaller or equal, it belongs to the smaller half (max-heap). Otherwise, it goes to the min-heap. This is shown in the operations column of the execution_table.

How is the median calculated when heaps have different sizes?

If heaps sizes differ by 1, median is the root of the larger heap. If equal, median is average of both roots. This is visible in the median column of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the median after adding number 1?

A 3.5

B 5

C 2

D 1

💡 Hint

Check the 'Median' column at step 4 in the execution_table.

At which step does the min-heap first get an element?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Min-Heap Nodes' column to see when min-heap changes from empty.

If we add a number smaller than all existing numbers, where will it be inserted?

A Either heap randomly

B Min-Heap

C Max-Heap

D It will replace the root of max-heap

💡 Hint

Refer to the 'Operation' and 'Number Added' columns and the rule comparing with max-heap root.

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 by comparing with max-heap root
- Balance heaps so size difference ≤ 1
- Median is root of larger heap or average of both roots
- Efficient for continuous median calculation in data streams

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, and the other (min-heap) stores the larger half. When a new number arrives, it is compared with the root of the max-heap to decide where to insert. After insertion, heaps are balanced to keep their sizes close. The median is then calculated from the roots of the heaps. This method allows quick median updates as numbers stream in.

Practice

1. What is the main purpose of using two heaps (a max-heap and a min-heap) in finding 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 efficiently keep track of the lower half and upper half of the numbers separately

D. To find the maximum number in 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 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 C

4. Quick Check:

   Two heaps split data halves = A [OK]

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

Common Mistakes:

• Thinking heaps sort all numbers fully
• Using one heap only
• Confusing max-heap and min-heap roles

2. Which of the following Go code snippets correctly initializes a max-heap and a min-heap for integers using container/heap package?

easy

A. maxHeap := &IntMaxHeap{}; minHeap := &IntMinHeap{}

B. maxHeap := heap.New(IntMaxHeap{}); minHeap := heap.New(IntMinHeap{})

C. maxHeap := &IntMinHeap{}; minHeap := &IntMaxHeap{}

D. maxHeap := make([]int, 0); minHeap := make([]int, 0)

Solution

1. Step 1: Recognize heap initialization in Go

   Heaps are initialized as pointers to custom heap types that implement heap.Interface.

2. Step 2: Identify correct syntax

   Using &IntMaxHeap{} and &IntMinHeap{} creates pointers to heap structs ready for heap operations.

3. Final Answer:

   maxHeap := &IntMaxHeap{}; minHeap := &IntMinHeap{} -> Option A

4. Quick Check:

   Pointer to heap struct = A [OK]

Hint: Use pointers to heap structs for container/heap [OK]

Common Mistakes:

• Using heap.New which does not exist
• Swapping max-heap and min-heap types
• Initializing as slices without heap.Interface

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

medium

A. 5

B. 8

C. 3

D. 4

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 (maxHeap top=5); insert 15 (minHeap top=15); insert 1 ≤5 (maxHeap top=5, contains 5,1); insert 3 ≤5 (maxHeap top=5, contains 5,1,3), balance: len=3 >1+1, pop 5 -> push minHeap top=5 (15,5), maxHeap top=3 (1,3).

2. Step 2: Calculate median from heaps

   Heaps sizes equal (2 each). Median = average of maxHeap top (3) and minHeap top (5) = (3+5)/2 = 4.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Median = (3+5)/2 = 4 [OK]

Hint: Median is average of two heap tops if sizes equal [OK]

Common Mistakes:

• Taking median as maxHeap top only
• Not balancing heaps after insertion
• Calculating median as sum instead of average

4. In the following Go code snippet for median calculation, what is the bug?

func addNum(num int) {
  if maxHeap.Len() == 0 || num <= (*maxHeap)[0] {
    heap.Push(maxHeap, num)
  } else {
    heap.Push(minHeap, num)
  }
  if maxHeap.Len() > minHeap.Len()+1 {
    heap.Push(minHeap, heap.Pop(maxHeap))
  } else if minHeap.Len() > maxHeap.Len() {
    heap.Push(maxHeap, heap.Pop(minHeap))
  }
}

medium

A. Heaps are not balanced after insertion

B. Comparison operator should be < instead of <=

C. heap.Pop returns interface{}, needs type assertion before Push

D. maxHeap and minHeap are swapped in conditions

Solution

1. Step 1: Analyze balancing logic

   The first condition correctly balances when maxHeap is too large (> minHeap.Len()+1). But the second condition checks minHeap.Len() > maxHeap.Len(), which triggers rebalance correctly when minHeap is larger.

2. Step 2: Why heaps are not balanced

   Original code used > maxHeap.Len() + 1 which fails to rebalance when minHeap is exactly one larger. Changing to > maxHeap.Len() fixes this.

3. Final Answer:

   Heaps are not balanced after insertion -> Option A

4. Quick Check:

   minHeap balance: > max.Len() [OK]

Hint: minHeap balance when len(min) > len(max) [OK]

Common Mistakes:

• Using +1 symmetrically for both balance conditions
• Wrong size difference in minHeap check
• Not balancing after every insertion

5. You want to find the median of a large data stream where numbers can be negative, zero, or positive. Which approach using two heaps ensures correct median calculation even with duplicates and negative values?

hard

A. Use a single max-heap and pop elements until median is found

B. Use a max-heap for lower half and min-heap for upper half, balance sizes, and calculate median from tops

C. Sort all numbers in an array and pick middle element(s) each time

D. Use two min-heaps and merge their outputs to find median

Solution

1. Step 1: Choose correct heap types for halves

   Max-heap stores lower half (including negatives), min-heap stores upper half, handling all values correctly.

2. Step 2: Balance heaps and compute median

   Keep heaps balanced in size; median is top of max-heap if odd count, or average of tops if even count.

3. Final Answer:

   Use a max-heap for lower half and min-heap for upper half, balance sizes, and calculate median from tops -> Option B

4. Quick Check:

   Two heaps balanced handle negatives and duplicates [OK]

Hint: Balance max and min heaps for all number ranges [OK]

Common Mistakes:

• Using two min-heaps which can't split halves properly
• Sorting entire stream each time (inefficient)
• Using single heap only