Median of Data Stream Using Two Heaps in DSA Java - 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 a list of numbers that keeps changing as new numbers come in. It uses two special lists called heaps to keep track of the smaller half and the larger half of the numbers. This way, you can quickly find the median without sorting the whole list every time. It works well even when numbers arrive one by one over time.

Why it matters

Without this method, finding the median in a changing list would be slow because you'd have to sort the entire list every time a new number arrives. This would make real-time data analysis, like tracking median temperatures or stock prices, very inefficient. Using two heaps makes it fast and practical to get the median instantly as data flows in.

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 for real-time analytics and statistics.

Mental Model

Core Idea

Keep the smaller half of numbers in a max-heap and the larger half in a min-heap so the median is always at the top of one or both heaps.

Think of it like...

Imagine two balanced baskets: one holds all the smaller apples, the other holds all the bigger apples. The median apple is the one right between these two baskets, easy to pick from the top of either basket.

┌───────────────┐       ┌───────────────┐
│   Max-Heap    │       │   Min-Heap    │
│ (smaller half)│       │ (larger half) │
│  [top = max]  │       │  [top = min]  │
└──────┬────────┘       └──────┬────────┘
       │                       │
       └───── Median ──────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Median Concept

Concept: Learn what median means in a list of numbers.

Median is the middle number when all numbers are sorted. If there is an odd count, it's the center number. If even, it's the average of the two center numbers.

Result

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

Understanding median is essential because it represents the center of data, which is what we want to find efficiently in a stream.

2

Foundation

Basics of Heaps (Priority Queues)

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

A max-heap always keeps the largest number at the top. A min-heap always keeps the smallest number at the top. Both allow quick access to these values.

Result

You can quickly get the largest or smallest number without sorting the whole list.

Knowing heaps lets you efficiently manage parts of data and quickly find extremes, which is key to finding medians fast.

3

Intermediate

Splitting Data into Two Heaps

Concept: Divide numbers into two groups: smaller half and larger half using two heaps.

Use a max-heap for the smaller half so the largest of the small numbers is on top. Use a min-heap for the larger half so the smallest of the large numbers is on top. This keeps data balanced around the median.

Result

You can access the middle values quickly by looking at the tops of the two heaps.

Splitting data this way keeps the median at the boundary, making it easy to find without sorting.

4

Intermediate

Balancing Heaps After Each Insertion

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

Concept: Keep the heaps balanced so their sizes differ by at most one to maintain correct median calculation.

After adding a new number, check heap sizes. If one heap is bigger by more than one, move the top element from the bigger heap to the smaller heap. This keeps the two halves balanced.

Result

Heaps stay balanced, ensuring the median is always at the top of one or both heaps.

Balancing heaps is crucial because an unbalanced split would give wrong median values.

5

Intermediate

Finding Median from Two Heaps

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

Concept: Calculate median based on heap sizes: if equal, average tops; if not, median is top of bigger heap.

If both heaps have the same size, median = (max-heap top + min-heap top) / 2. If one heap has one extra element, median = top of that heap.

Result

You get the median instantly without sorting all numbers.

Knowing how to get median from heaps sizes and tops lets you answer median queries in constant time.

6

Advanced

Java Implementation with PriorityQueue

🤔Before reading on: do you think Java's PriorityQueue is a max-heap or min-heap by default? Commit to your answer.

Concept: Use Java's PriorityQueue for min-heap and a custom comparator for max-heap to implement the two heaps.

In Java, PriorityQueue is a min-heap by default. To create a max-heap, use a comparator that reverses order. Insert numbers into appropriate heap, balance sizes, then compute median from tops.

Result

A runnable Java class that maintains median in a data stream efficiently.

Understanding Java's PriorityQueue behavior and how to customize it is key to implementing this algorithm correctly.

7

Expert

Handling Edge Cases and Performance

🤔Before reading on: do you think this method handles duplicate numbers and negative numbers correctly? Commit to yes or no.

Concept: The two heaps method naturally handles duplicates and negative numbers, but careful balancing and insertion order matter for performance.

Duplicates go into heaps like any other number. Negative numbers are handled naturally by heap ordering. Performance depends on balancing after each insertion. Worst-case insertion is O(log n), median retrieval is O(1).

Result

Robust median calculation that works for all integer inputs and large data streams efficiently.

Knowing that this method handles all number types and duplicates without extra code shows its robustness and production readiness.

Under the Hood

Internally, two heaps maintain partial orderings: max-heap stores the smaller half with the largest at top, min-heap stores the larger half with smallest at top. When a new number arrives, it is pushed into one heap based on comparison with current median. Then heaps are balanced by moving the top element from one heap to the other if size difference exceeds one. This ensures the median is always at the top of one or both heaps, allowing O(1) median retrieval. Heap insertions and removals take O(log n) time.

Why designed this way?

This design was chosen to avoid sorting the entire data stream repeatedly, which is costly. Using two heaps splits the problem into manageable halves, leveraging efficient priority queue operations. Alternatives like balanced binary search trees exist but are more complex to implement and maintain. The two heaps approach balances simplicity, efficiency, and ease of implementation.

┌───────────────┐ insert new number
│   New Number  │─────────────┐
└───────────────┘             │
                              ▼
                    ┌─────────────────┐
                    │ Compare with median│
                    └────────┬─────────┘
                             │
            ┌────────────────┴───────────────┐
            ▼                                ▼
   ┌─────────────────┐               ┌─────────────────┐
   │ Insert into max-heap │           │ Insert into min-heap │
   └─────────┬─────────┘           └─────────┬─────────┘
             │                               │
             ▼                               ▼
   ┌───────────────────────────────┐
   │ Check size difference > 1?     │
   └───────────────┬───────────────┘
                   │ yes
                   ▼
   ┌───────────────────────────────┐
   │ Move top element from bigger heap │
   │ to smaller heap                 │
   └───────────────────────────────┘
                   │
                   ▼
          ┌─────────────────┐
          │ Median = top(s) │
          └─────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think the median is always the average of the two heap tops? Commit yes or no.

Common Belief: The median is always the average of the max-heap top and min-heap top.

Reality: The median is the average only when both heaps have the same size. If one heap has one extra element, the median is the top of that heap.

Why it matters: Misunderstanding this leads to wrong median values when the total number of elements is odd.

Quick: Do you think Java's PriorityQueue is a max-heap by default? Commit yes or no.

Common Belief: Java's PriorityQueue is a max-heap by default.

Reality: Java's PriorityQueue is a min-heap by default. To get a max-heap, you must provide a custom comparator that reverses the order.

Why it matters: Using PriorityQueue without a comparator for max-heap breaks the algorithm and causes incorrect median calculations.

Quick: Do you think duplicates cause errors in the two heaps method? Commit yes or no.

Common Belief: Duplicates cause the two heaps method to fail or give wrong medians.

Reality: Duplicates are handled naturally by heaps and do not cause errors or incorrect medians.

Why it matters: Believing duplicates break the method may cause unnecessary complex code or avoidance of this efficient approach.

Quick: Do you think balancing heaps means making them exactly equal in size? Commit yes or no.

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

Reality: Heaps can differ in size by one element; exact equality is not required.

Why it matters: Trying to force exact equality complicates the code and is unnecessary for correct median calculation.

Expert Zone

1

The choice of which heap to insert a new number into depends on comparing with the current median, not just the heap tops, to maintain balance and correctness.

2

When balancing heaps, moving the top element between heaps is an O(log n) operation, but median retrieval remains O(1), making this approach efficient for large streams.

3

In multi-threaded environments, synchronization around heap operations is critical to avoid race conditions, which is often overlooked in simple implementations.

When NOT to use

This method is not ideal when data is static or when you need other statistics like mode or mean. For static data, sorting once is simpler. For mode, frequency maps are better. Also, if memory is very limited, maintaining two heaps may be costly; approximate streaming algorithms like count-min sketch might be preferred.

Production Patterns

In real systems, this method is used in real-time analytics dashboards, financial tickers, and sensor data processing where median latency or median value is critical. It is often combined with sliding window techniques to find median over recent data only.

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 can support more operations like order statistics beyond median.

Streaming Algorithms

Builds on the idea of processing data one element at a time efficiently.

Knowing two heaps median method is a foundational streaming algorithm that introduces concepts used in more complex streaming statistics.

Load Balancing in Computer Networks

Both involve balancing loads or data between two groups to optimize performance.

Recognizing balancing heaps is like balancing network loads helps understand the importance of even distribution for efficiency.

Common Pitfalls

#1 Inserting new numbers without balancing heaps afterward.

Wrong approach:

maxHeap.add(num);
minHeap.add(num); // adding to both without balancing
// no size check or element movement

Correct approach:

if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
// Balance sizes
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.add(maxHeap.poll());
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.add(minHeap.poll());
}

Root cause:

Not understanding that heaps must be balanced after each insertion to maintain correct median calculation.

#2 Using Java PriorityQueue as max-heap without a comparator.

Wrong approach:

PriorityQueue maxHeap = new PriorityQueue<>(); // default min-heap
maxHeap.add(num);

Correct approach:

PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(num);

Root cause:

Assuming PriorityQueue is max-heap by default, leading to incorrect ordering and median errors.

#3 Calculating median always as average of two heap tops regardless of sizes.

Wrong approach:

double median = (maxHeap.peek() + minHeap.peek()) / 2.0;

Correct approach:

if (maxHeap.size() == minHeap.size()) {
median = (maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
median = maxHeap.peek();
}

Root cause:

Ignoring that median depends on heap sizes, causing wrong median when total count is odd.

Key Takeaways

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

Balancing the heaps so their sizes differ by at most one ensures the median is always at the top of one or both heaps.

Java's PriorityQueue is a min-heap by default; to create a max-heap, a custom comparator is necessary.

Median retrieval is O(1) after O(log n) insertion, making this method suitable for real-time streaming data.

Understanding heap balancing and median calculation rules prevents common mistakes and ensures correct results.

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 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 for median calculation

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 median calculation

   By balancing these heaps, the median can be found quickly from the top elements of the heaps.

3. Final Answer:

   To efficiently keep track of the lower half and upper half of the numbers for median calculation -> Option C

4. Quick Check:

   Two heaps split data for median [OK]

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

Common Mistakes:

• Thinking heaps sort all numbers completely
• Using only one heap for median
• Confusing max heap and min heap roles

2. Which of the following Java code snippets correctly initializes a max heap using PriorityQueue for the Median of Data Stream problem?

easy

A. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

B. PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

C. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.naturalOrder());

D. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.naturalOrder());

Solution

1. Step 1: Identify max heap initialization

   Java's PriorityQueue is a min heap by default; to make max heap, use Collections.reverseOrder().

2. Step 2: Check options

   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); uses Collections.reverseOrder(), which correctly creates a max heap.

3. Final Answer:

   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); -> Option A

4. Quick Check:

   Max heap needs reverse order comparator [OK]

Hint: Use Collections.reverseOrder() for max heap in Java [OK]

Common Mistakes:

• Using default PriorityQueue without comparator
• Using naturalOrder() which is min heap
• Using Collections.naturalOrder() which doesn't exist

3. Consider the following Java code snippet for adding numbers to two heaps and finding the median:

MedianFinder mf = new MedianFinder();
mf.addNum(1);
mf.addNum(5);
mf.addNum(2);
System.out.println(mf.findMedian());

Assuming the MedianFinder class uses two heaps correctly, what will be the printed output?

medium

A. 2.5

B. 2

C. 3

D. 1

Solution

1. Step 1: Add numbers and balance heaps

   Numbers added: 1, 5, 2. Sorted order: 1, 2, 5. Median is middle number 2.

2. Step 2: Calculate median

   Since odd count, median is the root of the heap with one extra element, which is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Median of [1,2,5] is 2 [OK]

Hint: Median of odd count is middle element [OK]

Common Mistakes:

• Calculating average instead of middle for odd count
• Ignoring heap balancing
• Confusing median with mean

4. The following Java method is part of a MedianFinder class using two heaps. It is supposed to add a number and rebalance heaps. Identify the bug:

public void addNum(int num) {
    if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
        maxHeap.add(num);
    } else {
        minHeap.add(num);
    }
    if (maxHeap.size() > minHeap.size() + 1) {
        minHeap.add(maxHeap.poll());
    } else if (minHeap.size() > maxHeap.size()) {
        maxHeap.add(minHeap.poll());
    }
}

medium

A. Should check if maxHeap is empty before peek() to avoid NullPointerException

B. The addNum method should not add to minHeap when num equals maxHeap.peek()

C. The rebalance condition for minHeap size is incorrect; should be minHeap.size() > maxHeap.size() + 1

D. No bug, method works correctly

Solution

1. Step 1: Analyze addNum logic

   It adds to maxHeap if empty or num <= maxHeap.peek(), else to minHeap.

2. Step 2: Check rebalance conditions

   Rebalances if maxHeap is bigger by more than 1 or minHeap bigger than maxHeap.

3. Final Answer:

   No bug, method works correctly -> Option D

4. Quick Check:

   Correct heap balancing logic [OK]

Hint: Check heap sizes differ by at most one [OK]

Common Mistakes:

• Forgetting to check maxHeap empty before peek
• Incorrect rebalance size conditions
• Misplacing elements between heaps

5. You want to extend the MedianFinder class to handle a large data stream efficiently. Which approach improves performance when finding the median after every insertion?

hard

A. Use two balanced heaps to keep halves and rebalance after each insertion

B. Store all numbers in a list and sort it after each insertion

C. Use a single max heap to store all numbers

D. Use a hash map to count frequencies and calculate median from counts

Solution

1. Step 1: Evaluate approaches for median calculation

   Sorting after each insertion (Store all numbers in a list and sort it after each insertion) is costly (O(n log n)). Single heap or hash map do not support quick median.

2. Step 2: Explain two heaps efficiency

   Two heaps keep halves balanced, allowing O(log n) insertion and O(1) median retrieval.

3. Final Answer:

   Use two balanced heaps to keep halves and rebalance after each insertion -> Option A

4. Quick Check:

   Two heaps optimize median in data stream [OK]

Hint: Two heaps give fast median updates in streams [OK]

Common Mistakes:

• Sorting entire list each time
• Using single heap only
• Ignoring insertion cost