Simultaneous Heaps for Problem Solving

Welcome back! In our last lesson, we saw how a single heap can efficiently solve "Top K" problems by maintaining a fixed-size collection of the most relevant elements from a data stream. This gave us an $O(\log k)$ solution for finding the k-th largest element, a marked improvement over naive sorting methods.

Today, we will expand on that foundation to explore a more advanced and versatile pattern: the Two Heaps approach. Instead of managing one set of "top" elements, this pattern allows us to partition an entire collection into two halves and efficiently query the boundary between them. This capability is crucial for a different class of problems that are common in technical interviews and have direct applications in real-world data analysis.

Your goal for this lesson is to learn how to identify problems where maintaining a max-heap and a min-heap simultaneously is the most advantageous strategy. We'll analyze the underlying structure of these problems so you can recognize the pattern in the wild.

The Core Idea: Partitioning a Dataset

In the previous lesson, we cared only about the k largest elements. But what if a problem requires us to reason about the entire dataset, specifically its central point or a partition? For example, finding the median requires knowing the middle value(s), which implies a conceptual split of the data into a smaller half and a larger half.

The Two Heaps pattern addresses this by using two heaps working in concert:

1. A Max-Heap to store the smaller half of the numbers. Its root gives us the largest element in the smaller half in $O(1)$ time.
2. A Min-Heap to store the larger half of the numbers. Its root gives us the smallest element in the larger half in $O(1)$ time.

By keeping these two heaps balanced (i.e., their sizes are equal or differ by at most one), we gain constant-time access to the elements straddling the midpoint of the entire sorted dataset.

When Should You Think "Two Heaps"?

Recognizing the right pattern is a key skill for interviews. The Two Heaps approach is particularly powerful for specific types of problems that might otherwise seem to require frequent re-sorting of data.

The following resource provides a clear overview of scenarios where this pattern excels.

As you can see, the common thread is the need to maintain a separation within a dataset and have quick access to the elements at the boundary of that separation. Let's explore two classic problems that perfectly illustrate this.

Case Study 1: Finding the Median of a Data Stream

This is the canonical example of the Two Heaps pattern. It extends the "data stream" concept from our last lesson. Instead of the k-th largest element, we now need to find the median after each new element is added.

As described before, we'll use a max-heap (small) for the lower half and a min-heap (large) for the upper half.

The process for adding a number is:

1. Insert: Add the new number to one of the heaps. A simple rule is to add to the small (max-heap) first.
2. Balance: To maintain the property that everything in small is less than or equal to everything in large, we check if the new number violates this. If the top of small is now greater than the top of large, we move the top element from small to large.
3. Rebalance Sizes: Ensure the heaps' sizes differ by at most 1. If one heap becomes too large, move its root element to the other heap.

The article below provides a step-by-step walkthrough of this logic.

To see this in a more dynamic format, the following video explains the entire thought process, from the brute-force approach to the optimized two-heaps solution.

The key insight is that the median is always either the top of one heap or the average of the tops of both, which can be found in $O(1)$ time. The cost is paid during the add operation, which takes $O(\log n)$ time due to heap insertions.

Case Study 2: IPO (Resource Allocation)

The Two Heaps pattern isn't just for finding medians. It can also solve complex resource allocation and scheduling problems. The IPO problem (LeetCode 502) is a great example that should resonate with your interest in finance.

Problem: You have an initial capital W. You are given a list of projects, each with a required capital and an expected profit. You can undertake at most k distinct projects. To start a project, your current capital must be greater than or equal to its required capital. Your goal is to maximize your final capital.

Pattern Recognition:
At any point, the projects are divided into two sets:

1. Projects you can afford (your capital W is sufficient).
2. Projects you cannot afford yet.

To maximize your final capital, the greedy strategy is to always choose the most profitable project from the set you can currently afford. This is the crucial insight that points to a two-heap solution.

• We can use a Min-Heap to store all the unaffordable projects, ordered by their capital requirement. This allows us to efficiently find which projects become available as our capital W increases.
• We can use a Max-Heap to store the affordable projects, ordered by their profit. This allows us to quickly select the best project to undertake next.

The following video explains this elegant solution.

In this problem, the two heaps don't partition a single stream of numbers. Instead, they manage two distinct states of a set of items (affordable vs. unaffordable), showcasing the pattern's versatility.

How to Identify the Two Heaps Pattern

Based on these examples, here are the primary signals to look for when trying to determine if a problem fits the Two Heaps pattern:

1. Partitioning into Two Sets: The problem involves splitting a collection of elements into two parts based on some property (e.g., smaller half/larger half, affordable/unaffordable, completed/pending).
2. Efficient Access to Boundary Elements: You need frequent and fast access to the largest element of the first set and/or the smallest element of the second set.
3. Finding Medians or Middle Elements: This is the most direct application. If a problem asks for a running median or anything related to the "middle" of a dynamic set, think Two Heaps.
4. Greedy Choices from a Changing Pool: The problem involves making a series of greedy choices (like picking the max or min), but the pool of valid items to choose from changes after each choice. The IPO problem is a perfect example of this.

Conclusion

You have now seen how the Two Heaps pattern extends the utility of heaps from simply finding the "Top K" elements to managing partitions within a dataset. This powerful technique provides efficient solutions to problems that might otherwise require costly sorting operations.

Key Takeaways:

• The Two Heaps pattern uses a max-heap and a min-heap to divide a dataset into two logical halves.
• This structure provides $O(1)$ access to the boundary elements (the max of the small half and the min of the large half).
• It is the go-to pattern for problems involving running medians of data streams.
• It can also be applied to problems involving resource allocation or scheduling, where you need to greedily select from a dynamically changing pool of eligible items (e.g., the IPO problem).

In this lesson, we focused on identifying when to use this pattern. In our next session, we'll dive deep into the implementation details, focusing on writing a clean, robust solution for the "Find Median from Data Stream" problem, including the critical balancing logic.