Median of Data Stream Using Two Heaps in DSA C#

Mental Model

Keep two heaps to split numbers into smaller half and larger half so the median is easy to find.

Analogy: Imagine a seesaw balanced in the middle with smaller kids on one side and bigger kids on the other side. The balance point is the median.

MaxHeap (smaller half): 10 -> 5 -> 3
MinHeap (larger half): 12 -> 15 -> 20
Median is between top of both heaps.

Dry Run Walkthrough

Input: Stream: 5, 15, 1, 3

Goal: Find median after each number is added

Step 1: Add 5 to max heap (smaller half)

MaxHeap: 5
MinHeap: empty

Why: Start by adding first number to smaller half

Step 2: Add 15 to min heap (larger half)

MaxHeap: 5
MinHeap: 15

Why: Add next number to larger half to keep balance

Step 3: Add 1 to max heap (smaller half)

MaxHeap: 5 -> 1
MinHeap: 15

Why: Add smaller number to smaller half

Step 4: Balance heaps sizes if needed (max heap has 2, min heap has 1, balanced)

MaxHeap: 5 -> 1
MinHeap: 15

Why: Heaps size difference is acceptable (<=1)

Step 5: Add 3 to max heap, then move top from max heap to min heap to balance

MaxHeap: 3 -> 1
MinHeap: 5 -> 15

Why: Max heap got too big, move largest from smaller half to larger half

Result:

MaxHeap: 3 -> 1
MinHeap: 5 -> 15
Median after last insertion: (3 + 5) / 2 = 4

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class MedianFinder {
    private PriorityQueue<int, int> maxHeap; // smaller half (max at top)
    private PriorityQueue<int, int> minHeap; // larger half (min at top)

    public MedianFinder() {
        maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        minHeap = new PriorityQueue<int, int>();
    }

    public void AddNum(int num) {
        if (maxHeap.Count == 0 || num <= maxHeap.Peek()) {
            maxHeap.Enqueue(num, -num); // add to smaller half with negative priority for max heap behavior
        } else {
            minHeap.Enqueue(num, num); // add to larger half
        }

        // Balance sizes: maxHeap can have 1 more element than minHeap
        if (maxHeap.Count > minHeap.Count + 1) {
            int moved = maxHeap.Dequeue();
            minHeap.Enqueue(moved, moved); // move top from smaller half to larger half
        } else if (minHeap.Count > maxHeap.Count) {
            int moved = minHeap.Dequeue();
            maxHeap.Enqueue(moved, -moved); // move top from larger half to smaller half
        }
    }

    public double FindMedian() {
        if (maxHeap.Count > minHeap.Count) {
            return maxHeap.Peek(); // odd count, median is top of smaller half
        } else {
            return (maxHeap.Peek() + minHeap.Peek()) / 2.0; // even count, average tops
        }
    }

    public static void Main() {
        MedianFinder mf = new MedianFinder();
        int[] stream = {5, 15, 1, 3};
        foreach (int num in stream) {
            mf.AddNum(num);
            Console.WriteLine($"Median after adding {num}: {mf.FindMedian()}");
        }
    }
}

if (maxHeap.Count == 0 || num <= maxHeap.Peek()) { maxHeap.Enqueue(num, -num); } else { minHeap.Enqueue(num, num); }

Add number to correct heap based on comparison with max of smaller half; use negative priority for max heap behavior

if (maxHeap.Count > minHeap.Count + 1) { int moved = maxHeap.Dequeue(); minHeap.Enqueue(moved, moved); } else if (minHeap.Count > maxHeap.Count) { int moved = minHeap.Dequeue(); maxHeap.Enqueue(moved, -moved); }

Balance heaps so size difference is at most 1

if (maxHeap.Count > minHeap.Count) { return maxHeap.Peek(); } else { return (maxHeap.Peek() + minHeap.Peek()) / 2.0; }

Calculate median based on heap sizes

Output

Median after adding 5: 5

Median after adding 15: 10

Median after adding 1: 5

Median after adding 3: 4

Complexity Analysis

Time: O(log n) per insertion because adding to heaps and balancing takes logarithmic time

Space: O(n) because all numbers are stored in the two heaps

vs Alternative: Compared to sorting all numbers each time (O(n log n)), this approach is faster for streaming data

Edge Cases

Empty stream

FindMedian should not be called or should handle empty gracefully (not shown here)

DSA C#

if (maxHeap.Count == 0 || num <= maxHeap.Peek()) { maxHeap.Enqueue(num, -num); }

All numbers equal

Heaps balance normally, median is that number

DSA C#

if (maxHeap.Count > minHeap.Count + 1) { ... } else if (minHeap.Count > maxHeap.Count) { ... }

Stream with negative and positive numbers

Heaps handle any integers correctly

DSA C#

if (maxHeap.Count == 0 || num <= maxHeap.Peek()) { maxHeap.Enqueue(num, -num); }

When to Use This Pattern

When you need to find the median of a growing list of numbers efficiently, use two heaps to keep track of smaller and larger halves for quick median calculation.

Common Mistakes

Mistake: Not balancing the heaps after insertion, causing incorrect median calculation
Fix: Always balance heaps so their sizes differ by at most one after each insertion

Mistake: Adding all numbers to one heap without splitting
Fix: Split numbers into two heaps based on comparison with max of smaller half

Summary

It finds the median of a stream of numbers by keeping two heaps for smaller and larger halves.

Use it when you want to get the median quickly after each new number in a stream.

The key is to keep the two heaps balanced so the median is always at the top of one or average of both.

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 remove duplicates from the data stream

B. To sort the entire data stream before finding the median

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

D. To efficiently find the median by balancing smaller and larger halves of the data

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

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

3. Final Answer:

   To efficiently find the median by balancing smaller and larger halves of the data -> Option D

4. Quick Check:

   Two heaps balance halves = median found efficiently [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
• Confusing median with mean

2. Which of the following C# code snippets correctly declares a max-heap using PriorityQueue for the Median of Data Stream problem?

easy

A. var maxHeap = new PriorityQueue();

B. var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => b - a));

C. var maxHeap = new PriorityQueue(Comparer<int>.Create((a, b) => a - b));

D. var maxHeap = new PriorityQueue(Comparer<int>.Default);

Solution

1. Step 1: Understand PriorityQueue default behavior

   By default, PriorityQueue in C# is a min-heap based on priority values.

2. Step 2: Creating a max-heap requires reversing comparison

   Using Comparer<int>.Create((a, b) => b - a) reverses order to make a max-heap.

3. Final Answer:

   var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a)); -> Option B

4. Quick Check:

   Reverse comparer creates max-heap [OK]

Hint: Reverse comparer for max-heap in C# PriorityQueue [OK]

Common Mistakes:

• Using default comparer creates min-heap, not max-heap
• Confusing type parameters in PriorityQueue
• Not providing comparer for max-heap

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

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 -> maxHeap=[5]; 15 -> minHeap=[15]; 1 ≤ max.top(5) -> maxHeap=[5,1] top=5; 3 ≤5 -> maxHeap=[5,1,3] top=5 (size 3 vs 1). Balance: move max.top=5 to minHeap -> maxHeap=[3,1] top=3, minHeap=[15,5] top=5.

2. Step 2: Calculate median from heaps

   maxHeap top = 3, minHeap top = 5. Median = (3 + 5) / 2 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

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

Hint: Median is average of two middle values when even count [OK]

Common Mistakes:

• Not balancing heaps after each insertion
• Taking median as middle element without averaging
• Mixing up maxHeap and minHeap tops

4. Consider this buggy C# code snippet for adding a number to the two heaps. What is the main error?

if (maxHeap.Count == 0 || num <= maxHeap.Peek())
    maxHeap.Enqueue(num, num);
else
    minHeap.Enqueue(num, num);

// Balance heaps
if (maxHeap.Count > minHeap.Count + 1)
    minHeap.Enqueue(maxHeap.Dequeue(), maxHeap.Dequeue());
else if (minHeap.Count > maxHeap.Count)
    maxHeap.Enqueue(minHeap.Dequeue(), minHeap.Dequeue());

medium

A. Enqueue uses wrong priority values

B. Using <= instead of < causes wrong heap insertion

C. Calling Dequeue() twice when balancing heaps causes errors

D. Not checking if heaps are empty before Peek()

Solution

1. Step 1: Analyze balancing code

   When balancing, code calls Dequeue() twice to move one element, which removes two elements incorrectly.

2. Step 2: Correct balancing approach

   Only one Dequeue() should be called to move one element from one heap to the other.

3. Final Answer:

   Calling Dequeue() twice when balancing heaps causes errors -> Option C

4. Quick Check:

   Double Dequeue removes two elements instead of one [OK]

Hint: Balance heaps by moving one element, not two [OK]

Common Mistakes:

• Calling Dequeue twice instead of once
• Ignoring heap size difference rules
• Incorrect comparison operators for insertion

5. You have a data stream of integers where duplicates are allowed. How does the two heaps approach handle duplicates when calculating the median, and what is the median after inserting [2, 2, 3, 4, 4, 4]?

hard

A. Duplicates are stored normally; median is 3.5

B. Duplicates are ignored; median is 2

C. Duplicates cause errors; median cannot be found

D. Duplicates are stored only once; median is 4

Solution

1. Step 1: Understand handling of duplicates in heaps

   Duplicates are stored like any other number; heaps do not remove duplicates automatically.

2. Step 2: Insert numbers and find median

   Numbers: [2, 2, 3, 4, 4, 4]. Sorted: [2, 2, 3, 4, 4, 4]. Median is average of 3rd and 4th elements: (3 + 4) / 2 = 3.5.

3. Final Answer:

   Duplicates are stored normally; median is 3.5 -> Option A

4. Quick Check:

   Duplicates stored; median of [2,2,3,4,4,4] = 3.5 [OK]

Hint: Duplicates do not affect heap logic; median from sorted data [OK]

Common Mistakes:

• Assuming duplicates are removed automatically
• Calculating median incorrectly with duplicates
• Confusing median with mode