Skip to main content

Introduction to Two Heaps

· 4 min read
Mr. Frugal
Mr. Frugal
I'm afraid of paying full price.

About the Pattern​

The two heaps pattern is a versatile and efficient approach for solving problems involving dynamic data processing, optimization, and real-time analysis. As the name suggests, this pattern uses two heaps, which could be:

  • Two min heaps
  • Two max heaps
  • A combination of one min heap and one max heap

By exploiting the heap property, this pattern is often used to implement computationally efficient solutions.

Key Properties of Heaps​

  • Insertion/Removal Complexity: O(log n), where n is the number of elements in the heap.
    • When adding a new element to the heap:
      • Insert it at the last position of the heap.
      • Restore the heap property by moving upward, comparing the element with its parent node (Heapify-Up).
  • Access Root Element: O(1).
    • Min Heap: Root stores the smallest element.
    • Max Heap: Root stores the largest element.

Common Use Case​

Given a dataset, the two heaps pattern can be used to divide it into two parts and efficiently find:

  • The smallest value from one part (using a min heap).
  • The largest value from the other part (using a max heap).

Other scenarios include finding:

  • The two largest numbers from two datasets (using two max heaps).
  • The two smallest numbers from two datasets (using two min heaps).

These examples highlight the pattern's flexibility for solving various problems by enabling quick access to minima and maxima as needed.

Examples​

1. Sliding Window Median​

Given an array of integers and a window size k, find the median of each sliding window of size k as it moves from left to right through the array.

2. Find Median of a Number Stream​

Given a continuous stream of numbers, efficiently find the median of the numbers seen so far after any insertion.

  1. Insert the new data into the Max-Heap first.
  2. If the root value of the Max-Heap is greater than the root value of the Min-Heap, move the largest value from the Max-Heap to the Min-Heap to maintain the correct order.
  3. Adjust the sizes of the two heaps to maintain balance:
  4. The size of the Max-Heap should be at most 1 greater than the size of the Min-Heap. Median Calculation: If the sizes of the two heaps are equal, return (Max-Heap root+Min-Heap root)/2 If the Max-Heap is larger, return the root of the Max-Heap.

Does Your Problem Match This Pattern?​

Applicable Scenarios​

The two heaps pattern applies if:

  1. Static or Streaming Data:
    • Linear Data: Input data is linear but not sorted. (If sorted, this pattern isn’t required.)
    • Stream of Data: Input is a continuous data stream.
  2. Maxima and Minima Calculation:
    • The input can be divided into two parts, requiring repeated calculations for:
      • Two maxima.
      • Two minima.
      • One maximum and one minimum.

Real-World Problems​

1. Video Platforms​

For demographic studies, calculate the median age of viewers efficiently as new users sign up for video streaming.

2. Gaming Matchmaking​

Match players of similar skill levels for a balanced gaming experience. Use:

  • One heap for minimum skill levels.
  • One heap for maximum skill levels.

3. IPO Solution​

Efficiently select projects to maximize profits with the following steps:

  1. Initialize a Min-Heap: Store the project capital requirements.
  2. Identify Feasible Projects: Find projects investable within the current capital range.
  3. Select the Most Profitable Project: Choose the project yielding the highest profit.
  4. Update Capital: Add the earned profit to the current capital.
  5. Repeat Until Target Achieved: Continue until k projects are selected.