Two Heaps: Solving Data Stream Problems

In our previous lessons, we've explored how heaps can efficiently solve problems involving the "top K" elements and merging k sorted streams. We saw that a single heap excels at maintaining a small, ordered subset of a larger collection. Now, we'll expand on this by using two heaps in tandem to solve a classic and highly relevant problem for real-time systems.

This lesson introduces the Two Heaps pattern. You will learn how to use a max-heap and a min-heap together to efficiently partition a set of numbers and find the median of a data stream. This is a common requirement in monitoring and analytics systems, where you might need to calculate the median latency of API requests or the median transaction value in real-time, without storing and re-sorting data constantly. This pattern is a staple of technical interviews for roles in scalable systems engineering.

1. The Challenge: Finding the Median in a Stream

Imagine you are responsible for a service that processes thousands of transactions per second. A key health metric is the median transaction processing time, updated every few seconds. How would you design a system to calculate this efficiently?

The problem, formally known as "Find Median from Data Stream," asks us to design a data structure with two primary operations:

• addNum(num): Adds a new number from a stream to our data structure.
• findMedian(): Returns the median of all numbers added so far.

The median is the middle value in a sorted list. If the list has an odd number of elements, it's the single middle element. If it's even, it's the average of the two middle elements.

A naive approach would be to keep all numbers in a list, and for every findMedian() call, sort the list and find the middle. This is extremely inefficient. A slightly better approach is to keep the list sorted upon insertion, but this still requires shifting elements, making each addNum operation slow, taking $O(N)$ time.

The following video introduces the problem and discusses this simple, but inefficient, brute-force solution, setting the stage for a more optimized approach.

2. The Two Heaps Insight

The key realization is that to find the median, we don't need the entire collection to be sorted. We only need to know the number(s) at the boundary between the smaller half and the larger half of the data.

This suggests we can partition the numbers into two "buckets":

1. A "lowers" bucket containing the smaller half of the numbers.
2. A "highers" bucket containing the larger half of the numbers.

To find the median, we would then need the largest number from the "lowers" bucket and the smallest number from the "highers" bucket. This is a perfect use case for heaps:

• We can use a Max-Heap to represent the "lowers" bucket, allowing us to find its largest element in $O(1)$ time.
• We can use a Min-Heap to represent the "highers" bucket, allowing us to find its smallest element in $O(1)$ time.

This structure is maintained by two strict rules:

1. Ordering Invariant: Every number in the max-heap (lowers) is less than or equal to every number in the min-heap (highers).
2. Size Invariant: The heaps must be kept balanced, with their sizes being either equal or differing by at most one.

The video below gives an excellent conceptual overview of this "two buckets" idea and why heaps are the ideal data structure for implementing it.

3. The Algorithm in Action

With our two heaps set up, let's define how the addNum and findMedian operations work while preserving our two invariants.

The addNum(num) Operation

When a new number arrives, we must add it to one of the heaps and then rebalance them to maintain the invariants. A robust way to do this is:

1. Add to a Heap: Always add the new number to the max-heap (the "lowers").
2. Maintain Order: The largest element in the max-heap might now be larger than the smallest element in the min-heap, violating the ordering invariant. To fix this, we pop the largest element from the max-heap and push it onto the min-heap.
3. Maintain Balance: After the previous step, the min-heap might have grown too large, violating the size invariant. If the min-heap has more than one element more than the max-heap, we pop the smallest element from the min-heap and push it onto the max-heap.

This sequence ensures that both the ordering and size invariants are always restored after adding a new number.

The following resource provides a clear, written explanation of this logic.

Let's visualize the process. The image below shows a snapshot of adding the number 7 to our heaps.

The most crucial part of this is the rebalancing step, which ensures the heaps don't drift apart in size.

The findMedian() Operation

This part is simple and efficient. Thanks to our invariants, calculating the median just involves looking at the tops of the heaps:

• If the heap sizes are equal, it means we have an even number of elements. The median is the average of the top of the max-heap and the top of the min-heap.
• If the heap sizes are unequal, one heap will have exactly one more element. The median is simply the top of the larger heap.

The following video segment provides a full walkthrough of adding several numbers, showing the rebalancing logic and median calculation at each step.

4. Implementation and Complexity

Now let's turn to implementation. As you're proficient in Go and JavaScript, we can look at how this pattern is realized in both languages.

A common challenge is that many standard libraries provide a min-heap but not a max-heap. This is easily solved by negating numbers before pushing them to the heap that we want to act as a max-heap. When you pop a value, you negate it again to get the original number.

The following resource provides full implementations in several languages, including JavaScript, and also covers complexity and common pitfalls.

For a Go-specific implementation, the following resource tackles the equivalent "Prefix Medians" problem. Note that its definition of the median for an even-sized array is the lower of the two middle elements, a common variation in competitive programming. The underlying Two Heaps logic is identical.

Complexity Analysis

The efficiency of the Two Heaps pattern is what makes it so powerful:

• Time Complexity:

  • addNum(num): $O(\log N)$. Each operation involves at most a few heap pushes and pops, which take logarithmic time.
  • findMedian(): $O(1)$. This operation only requires peeking at the top elements of the heaps.

• Space Complexity: $O(N)$. We need to store all the numbers that have been added to the stream.

This is a massive improvement over the naive sorting-based approaches and is ideal for the high-throughput, low-latency requirements of scalable systems.

Conclusion

In this lesson, we dissected the Two Heaps pattern, a clever technique for maintaining a partitioned dataset to find a running median. By balancing a max-heap for the smaller half of numbers and a min-heap for the larger half, we can achieve highly efficient addNum and findMedian operations.

Key Takeaways:

• Problem: Efficiently find the median from a continuous stream of data.
• Pattern: Use two heaps—a max-heap for the "lowers" and a min-heap for the "highers".
• Invariants: The pattern relies on maintaining an ordering invariant (max of lowers ≤ min of highers) and a size invariant (heap sizes differ by at most one).
• Complexity: Achieves $O(\log N)$ for adding numbers and $O(1)$ for finding the median, making it highly suitable for real-time applications.
• Application: A core pattern for real-time analytics, monitoring systems, and a frequent topic in senior-level technical interviews.

In our next lesson, we will shift from heap-based patterns to advanced searching techniques. We'll start by exploring Modified Binary Search, learning how to apply it to problems involving rotated or non-traditionally sorted arrays.