Two Heaps; Min Heap & Max Heap
Introduction
This pattern helps in finding Medians from a stream of data; however, this pattern is also very efficient in places where you need to maximize item X while minimizing item Y. Like in the famous IPO problem in leetcode.
This pattern uses two Heaps to solve these problems; A Min Heap to find the smallest element and a Max Heap to find the largest element.
This article dissects the algorithm to find the sliding window median or median of a data stream by breaking the algorithm into four easy to understand steps/functions.
P.s the entire solution is written in Java.
What is a Median?
You can think of the median as the middle value in the sorted list; If there are an even number of elements in the list, then the median becomes the average of the two middle values.
eg → [1, 2 , 3, 4, 5] -> no. of elements = 5
Since the number of elements is odd, the median is the middle element = 3
eg 2 → [1, 2, 3, 4, 5, 6] -> no. of elements = 6
Since the number of elements is even, the median is the average of the two middle elements = (3 + 4)/2 = 3.5
What is a Heap?
Heaps are a complete binary tree where the root node either has the minimum or the maximum value.
Min-Heap: The root node has the minimum value. The value of each node is equal to or greater than the value of its parent node.
Max-Heap: The root node has the maximum value. The value of each node is equal to or less than the value of its parent node.
They have three functions, insert O(log N), remove O(log N), peek O(1). Where peek returns the top element of the heap.
//Java lets you create min and max heaps using the following syntax
maxHeap = new PriorityQueue<>((a, b) -> b - a);
minHeap = new PriorityQueue<>((a, b) -> a - b);Pattern highlight:
We will make use of the two heaps pattern to find the median value of a data stream, as it is the most time-efficient algorithm.
Where the Max Heap (Small numbers heap) and Min Heap (Large number list) will contain the lower and upper half of the elements accordingly. Hence, making it easier for us to compute the median at any instance.
[Remember: MAXHEAP WILL CONTAIN THE SMALLER HALF !]
If odd no. of elements → median = top element of Max Heap
If even no. of elements → median = (top element of Max Heap + top element of Min Heap)/2
We require four functions: Insert, remove, findMedian, and balanceHeaps.
insert(int x):
We insert the element into the Max Heap (small numbers) if its value is less than or equal to the max value of the Max Heap. Otherwise, we will insert into the Min Heap (big numbers).
However, after inserting, our heaps may be unbalanced. So, we use to balanceHeaps function to fix that. We will discuss that later in the article.
public void insert(int x){
// if X is smaller than the middle value or if maxHeap is empty
if (maxHeap.isEmpty() || maxHeap.peek() >= x)
maxHeap.add(x);
// if X is greater than the middle value
else
minHeap.add(x);
balanceHeaps();
}Time complexity for this step is O(log N).
remove(int x):
Just like insert, we need to find out which heap contains the element that we need to remove, and we rebalance the min and max heaps.
public void remove(int x){
//element exists in maxHeap
if (x <= maxHeap.peek())
maxHeap.remove(x);
// element exists in MinHeap
else
minHeap.remove(x);
balanceHeaps();
}Time complexity for this step is O(log n).
balanceHeaps():
This function makes sure that either both the heaps will have an equal number of elements or the max-heap will have one more element than the min-heap.
public void balanceHeaps(){
//if maxHeap has more than 1 element than minHeap
if (maxHeap.size() > minHeap.size() + 1)
minHeap.add(maxHeap.poll());
//if maxHeap has less elements than minHeap
else if (maxHeap.size() < minHeap.size())
maxHeap.add(minHeap.poll());
}Time complexity of this function is log N + log N = O(log N)
findMedian():
Since our heaps are already balanced, finding the median should be straightforward.
If odd no. of elements → median = top element of Max Heap
If even no. of elements → median = (top element of Max Heap + top element of Min Heap)/2
public double findMedian(){
//if even number of elements exist
if(maxHeap.size() == minHeap.size())
return ((double) maxHeap.peek() + minHeap.peek())/2;
//if odd number of elements exist
else
return maxHeap.peek();
}Time complexity for this step is O(1).
Space and Time Complexity
The space complexity for this pattern is O(N), as, at any given instance, the total number of elements in both the heaps combined doesn’t exceed N elements.
The time complexity for this pattern is O(N log N), as the most expensive step in this pattern is O(log N). In the worst case, all N steps cost log N time. Hence, the time complexity is O(N * log N) in the worst case.
Solutions
Although this pattern may seem very specific, it is quite common in interviews. Two famous interview questions require you to know this pattern.
Find median from a data stream (LC MEDIUM)
class MedianFinder{
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> a - b);
//Copy-paste function from the pattern
public void insert(int x){
if (maxHeap.isEmpty() || maxHeap.peek() >= x)
maxHeap.add(x);
else
minHeap.add(x);
balanceHeaps();
}
//Copy-paste function from the pattern
public double findMedian(){
if(maxHeap.size() == minHeap.size())
return ((double) maxHeap.peek() + minHeap.peek())/2;
else
return maxHeap.peek();
}
//Copy-paste function from the pattern
public void balanceHeaps(){
if (maxHeap.size() > minHeap.size() + 1)
minHeap.add(maxHeap.poll());
else if (maxHeap.size() < minHeap.size())
maxHeap.add(minHeap.poll());
}
}Sliding Window Median (LC HARD)
This problem is a combination of sliding window and median. Since we’ve already implemented the four functions to find the median, we only need to implement a sliding window here and compute the median.
class Solution{
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> a - b);
public double[] medianSlidingWindow(int[] nums, int k){
//result array would contain length - k + 1 elements
double[] result = new double[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
insert(nums[i]);
//if we have at least k elements
if (i - k + 1 > = 0) {
result[i - k + 1] = findMedian();
int elementToBeRemoved = nums[i - k + 1];
remove(elementToBeRemoved);
}
}
return result;
}
//copy paste the 4 pre defined functions here.
}Conclusion
I hope that the breaking of the median computing problem into four parts, Insert, Remove, findMedian, and balanceHeaps helped you understand the two heaps algorithm better.
Go ahead and rock all your interviews that require this pattern! 🙌
