Median of Data Stream Using Two Heaps in DSA C# - Deep Dive

Overview - Median of Data Stream Using Two Heaps

What is it?

Median of Data Stream Using Two Heaps is a method to find the middle value of numbers that keep coming in one by one. Instead of waiting for all numbers, it updates the middle value quickly after each new number. It uses two special lists called heaps to keep track of smaller and bigger halves of the numbers. This way, it can tell the median fast at any time.

Why it matters

Without this method, finding the median in a stream of numbers would mean sorting all numbers every time a new one arrives, which is slow and inefficient. This method solves the problem by organizing numbers smartly so the median is always easy to find. It is useful in real-time systems like stock prices, sensor data, or live statistics where quick answers matter.

Where it fits

Before learning this, you should understand basic data structures like arrays and heaps (priority queues). After this, you can explore other streaming algorithms or advanced data structures like balanced trees or order statistics trees.

Mental Model

Core Idea

Keep the smaller half of numbers in a max-heap and the larger half in a min-heap to quickly find the median by balancing their sizes.

Think of it like...

Imagine two baskets: one holds all the smaller apples, the other holds all the bigger apples. By keeping the baskets balanced, you can always pick the middle apple easily without sorting all apples every time.

┌───────────────┐       ┌───────────────┐
│   Max-Heap    │       │   Min-Heap    │
│ (Smaller half)│       │ (Larger half) │
│  [max at top] │       │  [min at top] │
└───────┬───────┘       └───────┬───────┘
        │                       │
        │                       │
        └────── Balance ────────┘
               │
               ▼
          Median is either
    top of max-heap, top of min-heap,
    or average of both depending on size.

Build-Up - 7 Steps

1

Foundation

Understanding Median Concept

Concept: Learn what median means and how to find it in a fixed list of numbers.

Median is the middle value in a sorted list. If the list has an odd number of elements, median is the middle one. If even, median is the average of the two middle values. For example, in [1, 3, 5], median is 3. In [1, 3, 5, 7], median is (3+5)/2 = 4.

Result

You can find the median by sorting and picking the middle value(s).

Understanding median in a fixed list sets the foundation for finding median in a changing list or stream.

2

Foundation

Basics of Heaps (Priority Queues)

Concept: Learn what heaps are and how max-heap and min-heap work.

A heap is a special tree-based structure where the parent is always bigger (max-heap) or smaller (min-heap) than its children. Max-heap lets you quickly find the largest element; min-heap lets you find the smallest. They support fast insertion and removal of the top element.

Result

You can efficiently get the largest or smallest number from a collection.

Knowing heaps is crucial because they let us keep track of halves of numbers efficiently.

3

Intermediate

Splitting Numbers into Two Heaps

Concept: Divide incoming numbers into two heaps to separate smaller and larger halves.

When a new number arrives, compare it with the max of the smaller half (max-heap). If smaller or equal, add it to max-heap; else add to min-heap. This keeps smaller numbers in max-heap and larger numbers in min-heap.

Result

Numbers are split so max-heap holds smaller half, min-heap holds larger half.

Separating numbers this way allows quick access to middle values without sorting all numbers.

4

Intermediate

Balancing the Two Heaps

🤔Before reading on: do you think the two heaps should always have the same number of elements? Commit to yes or no.

Concept: Keep the sizes of the two heaps balanced so median calculation is simple.

After adding a number, if one heap has more than one extra element compared to the other, move the top element from the bigger heap to the smaller heap. This keeps their sizes equal or off by one.

Result

Heaps remain balanced in size, ensuring median is either top of one heap or average of both tops.

Balancing heaps is key to maintaining the correct median without reprocessing all numbers.

5

Intermediate

Calculating Median from Heaps

🤔Before reading on: if max-heap has one more element than min-heap, is median the top of max-heap or min-heap? Commit to your answer.

Concept: Use the sizes of heaps to decide how to find the median.

If heaps have equal size, median is average of max-heap top and min-heap top. If one heap has one extra element, median is the top of that heap.

Result

Median is found in O(1) time from the heaps' top elements.

Knowing how to pick median from heaps' tops avoids sorting or scanning all numbers.

6

Advanced

Implementing Median Finder in C#

🤔Before reading on: do you think C# has built-in max-heap? Commit yes or no.

Concept: Use C# PriorityQueue with custom comparers to implement max-heap and min-heap for median calculation.

C# PriorityQueue is a min-heap by default. To create a max-heap, invert the comparison by using a custom comparer. Insert numbers into appropriate heaps, balance them, and calculate median as explained. Example code: using System; using System.Collections.Generic; public class MedianFinder { private PriorityQueue maxHeap; // smaller half private PriorityQueue minHeap; // larger half public MedianFinder() { maxHeap = new PriorityQueue(Comparer.Create((a,b) => b.CompareTo(a))); minHeap = new PriorityQueue(); } public void AddNum(int num) { if (maxHeap.Count == 0 || num <= maxHeap.Peek()) { maxHeap.Enqueue(num, num); } else { minHeap.Enqueue(num, num); } // Balance heaps if (maxHeap.Count > minHeap.Count + 1) { int val = maxHeap.Dequeue(); minHeap.Enqueue(val, val); } else if (minHeap.Count > maxHeap.Count) { int val = minHeap.Dequeue(); maxHeap.Enqueue(val, val); } } public double FindMedian() { if (maxHeap.Count > minHeap.Count) { return maxHeap.Peek(); } else { return (maxHeap.Peek() + minHeap.Peek()) / 2.0; } } } // Usage example: // MedianFinder mf = new MedianFinder(); // mf.AddNum(1); mf.FindMedian() -> 1 // mf.AddNum(5); mf.FindMedian() -> 3 // mf.AddNum(2); mf.FindMedian() -> 2

Result

You get a working C# class that adds numbers and returns median efficiently.

Knowing how to implement max-heap in C# using PriorityQueue and custom comparer is essential for this algorithm.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think balancing heaps after every insertion costs O(log n) or O(n)? Commit your answer.

Concept: Understand performance and edge cases like duplicate numbers, large streams, and integer overflow.

Balancing heaps after each insertion costs O(log n) because heap operations are logarithmic. Duplicate numbers are handled naturally by heaps. For very large streams, memory can grow, so consider sliding window median or approximate methods. Integer overflow can be avoided by using double for median calculation and careful casting.

Result

Algorithm remains efficient and correct even with tricky inputs and large data.

Knowing performance costs and edge cases prepares you for real-world use and optimization.

Under the Hood

The two heaps store numbers so that max-heap always contains the smaller half and min-heap the larger half. The heaps are balanced so their sizes differ by at most one. The median is either the top of the max-heap (if it has one extra element) or the average of the tops of both heaps. Internally, heap operations maintain the heap property by swapping elements up or down the tree structure, allowing O(log n) insertion and removal.

Why designed this way?

This design was chosen to avoid sorting the entire data stream after each insertion, which is costly. Using two heaps splits the problem into manageable parts and leverages efficient priority queue operations. Alternatives like balanced binary search trees exist but are more complex to implement and maintain. The two-heap method balances simplicity, speed, and memory use.

Incoming Number
     │
     ▼
┌───────────────┐
│ Compare with   │
│ max-heap top  │
└───────┬───────┘
        │
   ┌────┴─────┐
   │          │
   ▼          ▼
Max-Heap   Min-Heap
 (smaller)  (larger)
   │          │
   └────┬─────┘
        ▼
  Balance sizes
        │
        ▼
   Median from
  heap tops

Myth Busters - 4 Common Misconceptions

Quick: Does the median always come from the max-heap top? Commit yes or no.

Common Belief: Median is always the top element of the max-heap.

Reality: Median can be the average of the tops of both heaps if they have equal size.

Why it matters: Assuming median is always max-heap top leads to wrong answers when heaps are balanced.

Quick: Do you think heaps must be exactly the same size at all times? Commit yes or no.

Common Belief: Heaps must always have the same number of elements.

Reality: Heaps can differ by one element in size to handle odd total counts.

Why it matters: Forcing equal sizes breaks the algorithm and median calculation for odd counts.

Quick: Is it okay to just insert numbers into one heap and sort later? Commit yes or no.

Common Belief: You can insert all numbers into one heap and sort when needed.

Reality: Sorting all numbers after each insertion is inefficient and defeats the purpose of using heaps.

Why it matters: This leads to slow performance and is impractical for large or streaming data.

Quick: Does C# PriorityQueue support max-heap natively? Commit yes or no.

Common Belief: C# PriorityQueue supports max-heap out of the box.

Reality: C# PriorityQueue is a min-heap by default; max-heap requires custom comparer or tricks.

Why it matters: Not knowing this causes implementation errors or inefficient workarounds.

Expert Zone

1

Balancing heaps after every insertion ensures median queries are O(1), but insertion remains O(log n), which is optimal for streaming data.

2

Using a custom comparer for max-heap in C# PriorityQueue is more efficient than negating values, especially for complex data types.

3

In very large data streams, memory usage can be controlled by combining this method with sliding window techniques or approximate quantile algorithms.

When NOT to use

This method is not ideal when you need medians over a sliding window of fixed size; specialized data structures like balanced BSTs or segment trees are better. Also, if approximate medians are acceptable, algorithms like Count-Min Sketch or reservoir sampling are more memory efficient.

Production Patterns

In real systems, this approach is used in live analytics dashboards, financial tickers, and sensor monitoring where median updates must be fast. It is often combined with concurrency controls and memory management for robustness.

Connections

Balanced Binary Search Trees

Alternative data structure for maintaining ordered data and finding medians.

Understanding two heaps helps appreciate why balanced trees are more complex but offer additional operations like order statistics.

Streaming Algorithms

Builds on the idea of processing data on the fly without storing all of it.

Knowing median of data stream using heaps is a stepping stone to more advanced streaming summaries and sketches.

Real-time Sensor Data Processing

Practical application domain where median of data stream is critical for noise reduction and anomaly detection.

Understanding this algorithm helps design systems that react quickly to changing sensor inputs.

Common Pitfalls

#1 Not balancing heaps after insertion.

Wrong approach:

maxHeap.Enqueue(num, num);
// No balancing code here

Correct approach:

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

Root cause:

Forgetting to keep heaps balanced breaks the median calculation logic.

#2 Using C# PriorityQueue as max-heap without custom comparer.

Wrong approach:

var maxHeap = new PriorityQueue(); // default min-heap
maxHeap.Enqueue(num, num);

Correct approach:

var maxHeap = new PriorityQueue(Comparer.Create((a,b) => b.CompareTo(a)));
maxHeap.Enqueue(num, num);

Root cause:

Assuming PriorityQueue supports max-heap natively leads to incorrect ordering.

#3 Calculating median incorrectly when heaps have equal size.

Wrong approach:

if (maxHeap.Count == minHeap.Count) return maxHeap.Peek();

Correct approach:

if (maxHeap.Count == minHeap.Count) return (maxHeap.Peek() + minHeap.Peek()) / 2.0;

Root cause:

Ignoring that median is average of two middle values when count is even.

Key Takeaways

Median of data stream can be found efficiently by splitting numbers into two heaps: max-heap for smaller half and min-heap for larger half.

Balancing the heaps after each insertion ensures the median is always accessible in constant time from the tops of the heaps.

C# PriorityQueue is a min-heap by default; to implement max-heap, use a custom comparer or invert values.

This method avoids sorting the entire data stream repeatedly, making it suitable for real-time applications.

Understanding heap balancing and median calculation logic prevents common mistakes and ensures correct, efficient implementation.

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