Median of Data Stream Using Two Heaps in DSA C# - Build from Scratch

Median of Data Stream Using Two Heaps

📖 Scenario: Imagine you are building a system that receives numbers one by one, like scores from a game played live. You want to find the middle score (median) quickly after each new score arrives.

🎯 Goal: Build a program that keeps track of the median of a stream of numbers using two heaps: a max heap for the lower half and a min heap for the upper half.

📋 What You'll Learn

Create two heaps: a max heap called lowerHalf and a min heap called upperHalf.

Add numbers to the heaps so that the size difference is never more than one.

Balance the heaps after each insertion.

Calculate the median from the tops of the heaps.

Print the median after all numbers are added.

💡 Why This Matters

🌍 Real World

Finding the median quickly is useful in live data analysis like stock prices, sensor data, or game scores.

💼 Career

This technique is often asked in coding interviews and is useful for roles involving real-time data processing and algorithm optimization.

1

Create two heaps for storing numbers

Create a max heap called lowerHalf and a min heap called upperHalf using SortedSet<int> with custom comparers to simulate heaps.

DSA C#

// Create lowerHalf as a max heap and upperHalf as a min heap
// Your code here

Hint

Use SortedSet<int> with a comparer that reverses order for lowerHalf to act like a max heap.

2

Add a list of numbers to process

Create a list of integers called numbers with these exact values: 5, 15, 1, 3.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var lowerHalf = new SortedSet(Comparer.Create((a, b) => b.CompareTo(a)));
        var upperHalf = new SortedSet();

        // Create the list of numbers
        // Your code here
    }
}

Hint

Use new List<int> { 5, 15, 1, 3 } to create the list.

3

Add numbers to heaps and balance them

Write a foreach loop using number to iterate over numbers. For each number, add it to lowerHalf if it is empty or less than or equal to the max of lowerHalf. Otherwise, add it to upperHalf. Then balance the heaps so their sizes differ by at most one by moving the top element from one heap to the other if needed.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var lowerHalf = new SortedSet(Comparer.Create((a, b) => b.CompareTo(a)));
        var upperHalf = new SortedSet();

        var numbers = new List { 5, 15, 1, 3 };

        // Add numbers to heaps and balance
        // Your code here
    }
}

Hint

Use lowerHalf.Max and upperHalf.Min to get the top elements. Move elements between heaps to keep sizes balanced.

4

Calculate and print the median

Calculate the median as a double. If lowerHalf and upperHalf have the same size, median is the average of lowerHalf.Max and upperHalf.Min. Otherwise, median is the max of the larger heap. Print the median using Console.WriteLine(median).

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var lowerHalf = new SortedSet(Comparer.Create((a, b) => b.CompareTo(a)));
        var upperHalf = new SortedSet();

        var numbers = new List { 5, 15, 1, 3 };

        foreach (var number in numbers)
        {
            if (lowerHalf.Count == 0 || number  upperHalf.Count + 1)
            {
                int maxLower = lowerHalf.Max;
                lowerHalf.Remove(maxLower);
                upperHalf.Add(maxLower);
            }
            else if (upperHalf.Count > lowerHalf.Count + 1)
            {
                int minUpper = upperHalf.Min;
                upperHalf.Remove(minUpper);
                lowerHalf.Add(minUpper);
            }
        }

        // Calculate and print median
        // Your code here
    }
}

Hint

Check the sizes of both heaps. If equal, average the two top values. Otherwise, take the top of the bigger heap.

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