Using Two Heaps Pattern
1. Understanding Median Maintenance
The Two Heaps pattern is commonly used to solve problems involving finding the median of a data stream or maintaining the median efficiently as new elements are added. It uses two heaps:
- A max heap to store the smaller half of the numbers.
- A min heap to store the larger half of the numbers.
This ensures that:
- The root of the max heap is the largest number in the smaller half.
- The root of the min heap is the smallest number in the larger half.
By maintaining this balance, we can efficiently find the median:
- If both heaps have equal size, the median is the average of the two roots.
- If one heap has more elements, the median is the root of the larger heap.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Insert Element | Adds a new element to the appropriate heap and rebalances if needed. | O(log n) | O(n) |
| Find Median | Returns the median based on the root(s) of the heaps. | O(1) | O(1) |
Example: Inserting Elements and Finding Median
class MedianFinder {
constructor() {
this.maxHeap = new MaxHeap(); // stores smaller half
this.minHeap = new MinHeap(); // stores larger half
}
insert(num) {
if (this.maxHeap.isEmpty() || num <= this.maxHeap.peek()) {
this.maxHeap.insert(num);
} else {
this.minHeap.insert(num);
}
// Rebalance heaps
if (this.maxHeap.size() > this.minHeap.size() + 1) {
this.minHeap.insert(this.maxHeap.extract());
} else if (this.minHeap.size() > this.maxHeap.size() + 1) {
this.maxHeap.insert(this.minHeap.extract());
}
}
findMedian() {
if (this.maxHeap.size() === this.minHeap.size()) {
return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
} else if (this.maxHeap.size() > this.minHeap.size()) {
return this.maxHeap.peek();
} else {
return this.minHeap.peek();
}
}
}
// Example usage:
const mf = new MedianFinder();
mf.insert(5);
mf.insert(15);
mf.insert(10);
console.log(mf.findMedian()); // 10
Note: The heaps must be maintained to ensure that the max heap contains at most one more element than the min heap.
2. Finding Median from Data Stream
When dealing with a data stream, finding the median efficiently requires maintaining two heaps:
- A max heap for the smaller half of elements.
- A min heap for the larger half of elements.
This ensures that the median can be retrieved in O(1) time, and insertion takes O(log n) time.
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Insert Element | Add element to appropriate heap, balancing heaps if needed. | O(log n) | O(n) |
| Find Median | Return top of max heap if odd size, or average of both tops if even. | O(1) | O(1) |
Example: Inserting Elements and Finding Median
class MedianFinder {
constructor() {
this.maxHeap = new MaxHeap(); // stores smaller half
this.minHeap = new MinHeap(); // stores larger half
}
insert(num) {
if (this.maxHeap.isEmpty() || num <= this.maxHeap.peek()) {
this.maxHeap.insert(num);
} else {
this.minHeap.insert(num);
}
// Balance heaps
if (this.maxHeap.size() > this.minHeap.size() + 1) {
this.minHeap.insert(this.maxHeap.extractMax());
} else if (this.minHeap.size() > this.maxHeap.size() + 1) {
this.maxHeap.insert(this.minHeap.extractMin());
}
}
findMedian() {
if (this.maxHeap.size() === this.minHeap.size()) {
return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
} else if (this.maxHeap.size() > this.minHeap.size()) {
return this.maxHeap.peek();
} else {
return this.minHeap.peek();
}
}
}
// Example usage:
const mf = new MedianFinder();
mf.insert(5);
mf.insert(15);
mf.insert(1);
console.log(mf.findMedian()); // 5
mf.insert(10);
console.log(mf.findMedian()); // 7.5
Note: The heaps must be balanced to ensure that the median can always be found in constant time.
3. Finding Sliding Window Median
The Two Heaps pattern is particularly useful for finding the median in a sliding window of data. This approach uses two heaps:
- A max heap to store the smaller half of the numbers.
- A min heap to store the larger half of the numbers.
This ensures that the median can be efficiently retrieved from the tops of the heaps.
| Property | Description | Notes |
|---|---|---|
| Heaps | Max heap (smaller half) and min heap (larger half) | Used to maintain order and allow O(1) access to median |
| Median Access | Top of max heap or average of both heaps | Even window size: average of two middle elements; Odd window size: top of max heap |
| Time Complexity | O(n log k) | n is the number of elements, k is the window size |
| Space Complexity | O(k) | k is the window size |
Example: Sliding Window Median
const findSlidingWindowMedian = (nums, k) => {
const result = [];
const maxHeap = new MaxHeap(); // stores smaller half
const minHeap = new MinHeap(); // stores larger half
for (let i = 0; i < nums.length; i++) {
// Add new number to appropriate heap
if (!maxHeap.isEmpty() && nums[i] <= maxHeap.peek()) {
maxHeap.insert(nums[i]);
} else {
minHeap.insert(nums[i]);
}
// Rebalance heaps if needed
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.insert(maxHeap.extractMax());
} else if (minHeap.size() > maxHeap.size() + 1) {
maxHeap.insert(minHeap.extractMin());
}
// If window is full, calculate median
if (i >= k - 1) {
let median;
if (maxHeap.size() === minHeap.size()) {
median = (maxHeap.peek() + minHeap.peek()) / 2;
} else if (maxHeap.size() > minHeap.size()) {
median = maxHeap.peek();
} else {
median = minHeap.peek();
}
result.push(median);
// Remove the element going out of window
const elementToRemove = nums[i - k + 1];
if (elementToRemove <= maxHeap.peek()) {
maxHeap.remove(elementToRemove);
} else {
minHeap.remove(elementToRemove);
}
}
}
return result;
};
// Example usage:
const nums = [1, 3, -1, -3, 5, 3, 6, 7];
const k = 3;
console.log(findSlidingWindowMedian(nums, k)); // [1, -1, -1, 3, 5]
Note: The heaps must be rebalanced after each insertion and removal to ensure that the size difference between them does not exceed 1.
4. Scheduling Tasks with Cooldown
| Property | Description | Example |
|---|---|---|
| task | Task identifier or name | "task-1" |
| cooldownPeriod | Minimum time (in seconds) between task executions | 30 |
| lastExecutionTime | Timestamp of the last execution | 1678886400 |
Example: Scheduling a Task with Cooldown
const tasks = [];
function scheduleTask(taskId, cooldownSeconds) {
const now = Math.floor(Date.now() / 1000);
const lastTask = tasks.find(t => t.id === taskId);
if (!lastTask || now - lastTask.lastExecutionTime >= cooldownSeconds) {
tasks.push({
id: taskId,
lastExecutionTime: now
});
console.log(`Task ${taskId} scheduled`);
} else {
console.log(`Task ${taskId} is on cooldown`);
}
}
scheduleTask("task-1", 30); // Schedules task
scheduleTask("task-1", 30); // On cooldown
Note: The cooldown logic ensures that tasks are not executed more frequently than specified, preventing resource exhaustion or rate-limiting issues.
5. Finding Next Interval
| Property | Description | Example |
|---|---|---|
| next_interval | Represents the next interval in a sequence based on start time | [1, 3], [2, 4], [3, 5] |
| start_time | Start time of the interval | 1 |
| end_time | End time of the interval | 3 |
Example: Finding Next Interval
function findNextInterval(intervals) {
const result = [];
const maxStartHeap = new MaxHeap();
const maxEndHeap = new MaxHeap();
for (let i = 0; i < intervals.length; i++) {
const [start, end] = intervals[i];
maxStartHeap.push([start, i]);
maxEndHeap.push([end, i]);
}
for (let i = 0; i < intervals.length; i++) {
let nextIntervalIndex = -1;
const [currentEnd, currentEndIndex] = maxEndHeap.pop();
const [currentStart, currentStartIndex] = maxStartHeap.peek();
if (currentStart >= currentEnd) {
nextIntervalIndex = currentStartIndex;
}
result.push(nextIntervalIndex);
}
return result;
}
class MaxHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.bubbleUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const max = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return max;
}
peek() {
return this.heap[0];
}
bubbleUp(index) {
if (index === 0) return;
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex][0] < this.heap[index][0]) {
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
this.bubbleUp(parentIndex);
}
}
bubbleDown(index) {
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;
let maxIndex = index;
if (leftChild < this.heap.length && this.heap[leftChild][0] > this.heap[maxIndex][0]) {
maxIndex = leftChild;
}
if (rightChild < this.heap.length && this.heap[rightChild][0] > this.heap[maxIndex][0]) {
maxIndex = rightChild;
}
if (maxIndex !== index) {
[this.heap[index], this.heap[maxIndex]] = [this.heap[maxIndex], this.heap[index]];
this.bubbleDown(maxIndex);
}
}
}
// Example usage:
const intervals = [[1, 3], [2, 4], [3, 5]];
console.log(findNextInterval(intervals)); // Output: [1, 2, -1]
6. Maximizing Capital
Given a set of projects with required capitals and profits, the goal is to select up to k projects to maximize the final capital. This problem uses two heaps:
- A min-heap to track projects by their required capital (to find affordable projects).
- A max-heap to track the profits of affordable projects (to select the most profitable one).
| Property | Description | Values |
|---|---|---|
| k | Maximum number of projects to select | int |
| capital | Initial capital available | int |
| projects | List of projects, each with [capitalRequired, profit] |
Array<[number, number]> |
Example: Maximizing Capital
function findMaximizedCapital(k, capital, profits) {
const minCapitalHeap = new Heap((a, b) => a[0] - b[0]); // [capital, index]
const maxProfitHeap = new Heap((a, b) => b[0] - a[0]); // [profit]
for (let i = 0; i < profits.length; i++) {
minCapitalHeap.push([capital[i], i]);
}
let currentCapital = capital;
for (let i = 0; i < k; i++) {
while (minCapitalHeap.size() && minCapitalHeap.peek()[0] <= currentCapital) {
const project = minCapitalHeap.pop();
maxProfitHeap.push([profits[project[1]]]);
}
if (maxProfitHeap.size() === 0) break;
const maxProfit = maxProfitHeap.pop();
currentCapital += maxProfit[0];
}
return currentCapital;
}
// Example usage:
const k = 2;
const capital = [0, 1, 1];
const profits = [1, 2, 3];
console.log(findMaximizedCapital(k, capital, profits)); // Output: 5
Note: The algorithm ensures that only projects with capital less than or equal to the current capital are considered for selection. It always picks the most profitable project among affordable ones.
7. Finding Running Median
Use two heaps to efficiently maintain and retrieve the median of a dynamic data stream.
| Property | Description | Usage |
|---|---|---|
| Max Heap | Stores the smaller half of numbers | Allows quick access to the largest number in the lower half |
| Min Heap | Stores the larger half of numbers | Allows quick access to the smallest number in the upper half |
Example: Inserting Numbers and Finding Median
class MedianFinder {
constructor() {
this.maxHeap = new MaxHeap(); // Lower half
this.minHeap = new MinHeap(); // Upper half
}
insert(num) {
if (this.maxHeap.isEmpty() || num <= this.maxHeap.peek()) {
this.maxHeap.insert(num);
} else {
this.minHeap.insert(num);
}
// Rebalance heaps
if (this.maxHeap.size() > this.minHeap.size() + 1) {
this.minHeap.insert(this.maxHeap.extractMax());
} else if (this.minHeap.size() > this.maxHeap.size() + 1) {
this.maxHeap.insert(this.minHeap.extractMin());
}
}
findMedian() {
if (this.maxHeap.size() === this.minHeap.size()) {
return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
} else if (this.maxHeap.size() > this.minHeap.size()) {
return this.maxHeap.peek();
} else {
return this.minHeap.peek();
}
}
}
// Example usage:
const mf = new MedianFinder();
mf.insert(5);
mf.insert(15);
mf.insert(10);
console.log(mf.findMedian()); // 10
Note: The median is the middle value in an ordered list of numbers. For even-length lists, it's the average of the two middle values.
8. Balancing Min and Max Heaps
| Operation | Description | Time Complexity | Space Complexity |
|---|---|---|---|
| Insert Element | Adds element to appropriate heap and rebalances | O(log n) | O(1) |
| Get Median | Returns median from top elements of both heaps | O(1) | O(1) |
| Rebalance Heaps | Moves root of larger heap to smaller heap if size difference > 1 | O(1) | O(1) |
Example: Inserting Elements into Heaps
class TwoHeaps {
constructor() {
this.maxHeap = new MaxHeap(); // stores smaller half
this.minHeap = new MinHeap(); // stores larger half
}
insert(num) {
if (this.maxHeap.isEmpty() || num <= this.maxHeap.peek()) {
this.maxHeap.insert(num);
} else {
this.minHeap.insert(num);
}
// Rebalance heaps
if (this.maxHeap.size() > this.minHeap.size() + 1) {
this.minHeap.insert(this.maxHeap.extractMax());
} else if (this.minHeap.size() > this.maxHeap.size() + 1) {
this.maxHeap.insert(this.minHeap.extractMin());
}
}
getMedian() {
if (this.maxHeap.size() === this.minHeap.size()) {
return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
} else if (this.maxHeap.size() > this.minHeap.size()) {
return this.maxHeap.peek();
} else {
return this.minHeap.peek();
}
}
}
Note: The max heap stores the smaller half of numbers, and min heap stores the larger half. This ensures that the median can be efficiently retrieved by comparing the tops of both heaps.
9. Managing Priority Tasks with Heaps
| Operation | Description | Time Complexity | Code Example |
|---|---|---|---|
| Insert Task | Adds a task with priority to the heap | O(log n) | |
| Extract Min | Removes and returns the highest priority task | O(log n) | const highestPriority = minHeap.extractMin(); |
| Peek | Returns the highest priority task without removing it | O(1) | const nextTask = minHeap.peek(); |
Note: The MinHeap ensures that the task with the lowest numerical priority value is always at the top.