Two Heaps Pattern

Why this pattern matters for LeetCode

Finding the median of a stream seems to require sorting after every new number: O(n log n) per insert. Two heaps cuts that to O(log n) per insert. The trick: keep the smaller half in a max-heap and the larger half in a min-heap. The tops of the two heaps are always the two middle values. Rebalance whenever the sizes differ by more than one. The median is either the top of the larger heap, or the average of both tops.

What the Two Heaps pattern is

Two heaps maintains two priority queues: a max-heap holding the smaller half of the elements and a min-heap holding the larger half. When you insert a new element, place it into the correct heap and then rebalance so the size difference is at most one. The max-heap top is the largest element in the smaller half; the min-heap top is the smallest element in the larger half. Together they give O(1) median access and O(log n) insertions.

Reach for Two Heaps when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Two Heaps

• ✓Find Median from Data Stream — classic two-heap problem
• ✓Sliding Window Median — two heaps with element removal as the window moves
• ✓IPO / task scheduling where you want to greedily pick the best available item while staying within a constraint
• ✓Any problem that needs the maximum of the 'below median' elements and minimum of the 'above median' elements simultaneously

When NOT to use Two Heaps

• ✕You only need the overall median once — sort the array instead, O(n log n)
• ✕You need a specific percentile rather than the median — a sorted structure or order statistics tree is cleaner
• ✕The dataset is static and never grows — sort once and index the midpoint
• ✕You only need the maximum or minimum, not both simultaneously — a single heap is enough

Better alternative: If you only need one extreme (max or min), a single heap or sorted array suffices. For static data, just sort and index.

JavaScript code template

Running median — O(log n) addNum, O(1) findMedian

// JavaScript doesn't have a built-in heap — this shows the logic.
// In an interview use a MinHeap/MaxHeap class or a library.

class MedianFinder {
  constructor() {
    this.lowerMax = new MaxHeap(); // max-heap for the smaller half
    this.upperMin = new MinHeap(); // min-heap for the larger half
  }

  addNum(num) {
    // Route to the correct heap
    if (this.lowerMax.isEmpty() || num <= this.lowerMax.peek()) {
      this.lowerMax.push(num);
    } else {
      this.upperMin.push(num);
    }

    // Rebalance: sizes should differ by at most 1
    if (this.lowerMax.size() > this.upperMin.size() + 1) {
      this.upperMin.push(this.lowerMax.pop());
    } else if (this.upperMin.size() > this.lowerMax.size()) {
      this.lowerMax.push(this.upperMin.pop());
    }
  }

  findMedian() {
    if (this.lowerMax.size() === this.upperMin.size()) {
      return (this.lowerMax.peek() + this.upperMin.peek()) / 2;
    }
    return this.lowerMax.peek(); // lowerMax always has the extra element
  }
}

addNum routes the new element: if it belongs in the lower half, push to lowerMax; otherwise push to upperMin. Then rebalance by moving the top element from the larger heap to the smaller one if the difference exceeds 1. findMedian is O(1): for odd total size, lowerMax has the extra element and its top IS the median. For even size, average the two tops.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Create a max-heap (lower half) and a min-heap (upper half).
2. 2To add a number: compare to the max-heap's top to decide which heap it belongs in. Push it there.
3. 3Rebalance: if one heap is larger by more than 1, move its top element to the other heap.
4. 4After rebalancing, the invariant holds: lowerMax.size() >= upperMin.size() and lowerMax.size() <= upperMin.size() + 1.
5. 5To find the median: if sizes are equal, average the two tops. If lowerMax is larger, its top is the median.
6. 6Every addNum is O(log n); every findMedian is O(1).

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

Coming soon

• Find Median from Data Stream

  The defining two-heap problem: addNum inserts, findMedian reads the tops of the two balanced heaps.

  Coming soon
• Sliding Window Median

  Two heaps with lazy deletion: track elements leaving the window and ignore them during rebalance.

  Coming soon
• IPO

  Max-heap of available project profits + min-heap of project capital requirements — pick greedily each round.

  Coming soon

Common mistakes beginners make

• ✕Forgetting to rebalance after every insertion — the median will be wrong as soon as one heap becomes too large.
• ✕Routing to the wrong heap — a new element must be compared to the current max-heap top, not a fixed value, to decide which half it belongs in.
• ✕Using a sorted array instead — insertion into a sorted array is O(n). Heaps give O(log n) insertion, which matters for streams.
• ✕Assuming JavaScript has a built-in heap — it doesn't. You'll need to implement one or use an abstract description in interviews. Practice the heap push/pop logic separately.

Two Heaps vs Sorted Array for Running Median

Choose the right tool for the job.

Time and space complexity

Each insertion triggers at most one push and one pop on each heap. Heap push and pop are O(log n). The rebalance step moves at most one element, also O(log n). The median query just peeks at the tops of both heaps — O(1). Total space is O(n) since every element is stored in exactly one of the two heaps.

Frequently asked questions

Why does a max-heap hold the smaller half?

The max-heap gives O(1) access to the largest element in the smaller half — the left midpoint. The min-heap gives O(1) access to the smallest element in the larger half — the right midpoint. Choosing which heap type for which half is exactly this: max-heap for the left half so you can read the boundary quickly.

What does rebalancing do and when is it needed?

Rebalancing moves an element from the larger heap to the smaller one whenever the size difference exceeds 1. This maintains the invariant that lowerMax always has either the same count as upperMin or exactly one more. Without rebalancing the tops no longer represent the true median.

Does JavaScript have a built-in heap?

No. For interview purposes, describe the heap operations (push O(log n), pop O(log n), peek O(1)) and implement the two-heap logic. In practice, implement a simple binary heap class or use a priority queue library. Python has heapq; Java has PriorityQueue; C++ has priority_queue.

When is lowerMax bigger and when are they equal?

After inserting an odd number of elements, lowerMax has one extra (total size is odd, one heap must have the extra). After inserting an even number, both heaps are equal size. The invariant is lowerMax.size() === upperMin.size() or lowerMax.size() === upperMin.size() + 1. Never the other way.