Two Heaps Pattern — Find Median From a Data Stream

Q: Why push to the max-heap first and then transfer?

It removes every branch. Pushing to low and immediately moving its largest element to high guarantees the new value ends up on the correct side without comparing it to the current median, and it works when either heap is empty. A single size rebalance afterwards restores the invariant.

A small pattern with one big idea: when you need the middle of a changing dataset, keep the halves in two heaps facing each other. Sorting on every query is O(n log n) each time; this is O(log n) per insert and O(1) per query.

The idea

low — a max-heap holding the smaller half. Its root is the largest of the small

values.

high — a min-heap holding the larger half. Its root is the smallest of the large

values.

Keep them balanced in size, and the median is either low's root (odd count) or the average of both roots (even count). Everything at the boundary is instantly reachable; everything else stays unsorted, which is exactly the work you avoid.

Every value on the left is ≤ every value on the right, and the sizes differ by at most one — so the median is always at the two roots.

The implementation

Python's heapq is min-only, so low stores negated values.

import heapq

class MedianFinder:
    def __init__(self):
        self.low = []      # max-heap via negation: smaller half
        self.high = []     # min-heap: larger half

    def add_num(self, num):
        # 1. always push to low first, then hand its largest to high.
        #    Going through low guarantees the value lands on the correct
        #    side without any comparison against the current median.
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))

        # 2. rebalance: low may hold one extra, never one fewer.
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def find_median(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

class MedianFinder {
    // low holds the smaller half (max-heap), high the larger (min-heap).
    private final PriorityQueue<Integer> low =
        new PriorityQueue<>(Comparator.reverseOrder());
    private final PriorityQueue<Integer> high = new PriorityQueue<>();

    public void addNum(int num) {
        // Push through low, then hand its largest to high: no comparison
        // against the current median, and no empty-heap special case.
        low.offer(num);
        high.offer(low.poll());

        // Rebalance: low may hold one extra, never one fewer.
        if (high.size() > low.size()) low.offer(high.poll());
    }

    public double findMedian() {
        if (low.size() > high.size()) return low.peek();
        return (low.peek() + high.peek()) / 2.0;   // 2.0, not 2
    }
}

class MedianFinder {
    priority_queue<int> low;                                  // max-heap
    priority_queue<int, vector<int>, greater<int>> high;      // min-heap

public:
    void addNum(int num) {
        // Push through low, then hand its largest to high.
        low.push(num);
        high.push(low.top());
        low.pop();

        // Rebalance: low may hold one extra, never one fewer.
        if (high.size() > low.size()) {
            low.push(high.top());
            high.pop();
        }
    }

    double findMedian() {
        if (low.size() > high.size()) return low.top();
        return (low.top() + high.top()) / 2.0;   // 2.0, not 2
    }
};

class MedianFinder {
  constructor() {
    // No built-in heap in JS. These arrays are kept sorted, which makes
    // insertion O(n) rather than O(log n) — fine for moderate streams,
    // but implement a real binary heap if the input is large.
    this.low = [];    // smaller half, ascending (largest at the end)
    this.high = [];   // larger half, ascending (smallest at the front)
  }

  addNum(num) {
    this.#insert(this.low, num);
    this.#insert(this.high, this.low.pop());   // hand low's largest to high

    if (this.high.length > this.low.length) {
      this.#insert(this.low, this.high.shift());
    }
  }

  findMedian() {
    const lowTop = this.low[this.low.length - 1];
    if (this.low.length > this.high.length) return lowTop;
    return (lowTop + this.high[0]) / 2;
  }

  #insert(arr, value) {
    let lo = 0, hi = arr.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid] < value) lo = mid + 1;
      else hi = mid;
    }
    arr.splice(lo, 0, value);
  }
}

The push-then-transfer trick is what makes this short. The obvious version — compare against the current median, decide which heap, then rebalance — needs several branches and an empty-heap special case. Pushing through low unconditionally handles both.

The invariant

Two conditions, and every bug in this pattern is one of them broken:

Ordering: every value in low ≤ every value in high.
Size: len(low) == len(high) or len(low) == len(high) + 1.

Restore both after every insert and the median query stays O(1) forever.

Sliding Window Median

The Hard variant: the same two heaps, but elements leave as well as arrive. Heaps have no efficient arbitrary delete, so the standard technique is lazy deletion — record the value as removed in a hash map, and discard it when it surfaces at a root.

def prune(heap, to_remove, sign):
    while heap and to_remove.get(sign * heap[0], 0) > 0:
        to_remove[sign * heap[0]] -= 1
        heapq.heappop(heap)

/** Heaps cannot delete an arbitrary element, so mark it and discard it
    only when it surfaces at the root. Track effective sizes separately,
    or the balance check counts entries that are logically gone. */
private void prune(PriorityQueue<Integer> heap, Map<Integer, Integer> toRemove) {
    while (!heap.isEmpty() && toRemove.getOrDefault(heap.peek(), 0) > 0) {
        toRemove.merge(heap.peek(), -1, Integer::sum);
        heap.poll();
    }
}

/* Heaps cannot delete an arbitrary element, so mark it and discard it
   only when it surfaces at the root. */
void prune(priority_queue<int>& heap, unordered_map<int,int>& toRemove) {
    while (!heap.empty() && toRemove[heap.top()] > 0) {
        toRemove[heap.top()]--;
        heap.pop();
    }
}

/** Heaps cannot delete an arbitrary element, so mark it and discard it
    only when it surfaces at the root. Track effective sizes separately. */
function prune(heap, toRemove) {
  while (heap.length && (toRemove.get(heap[0]) ?? 0) > 0) {
    toRemove.set(heap[0], toRemove.get(heap[0]) - 1);
    heap.shift();
  }
}

Track the effective sizes separately from the raw heap lengths, or the balance check counts entries that are logically gone. In an interview it is fair to say a balanced BST or an order-statistic tree is the cleaner structure here, and that lazy deletion is the practical workaround.

IPO

The variant that shows the pattern is not only about medians: two heaps can also mean two different orderings of the same data. Keep projects in a min-heap by capital requirement, and as your capital grows, move everything now affordable into a max-heap by profit — then greedily take that heap's root. One heap answers "what can I afford", the other "what pays best".

Complexity

O(log n) per insert, O(1) per median query, O(n) space. Compare against re-sorting at O(n log n) per query, or an insertion into a sorted array at O(n) per insert — the two heaps beat both, and the reason is that you never sort what you do not need ordered.

Mistakes that cost the round

Forgetting to negate on the way in or on the way out of the max-heap.
Rebalancing before ordering. Sizes can be right while a value sits on the wrong side;

push through low first, then rebalance.

Integer division on the even-count median. Use float division.
Not deciding which heap keeps the extra element. Pick one, and make the query match.
Assuming heaps support delete. They do not — that is what lazy deletion is for.

What to drill

Find Median from Data Stream — the pattern, bare.
Sliding Window Median — with lazy deletion.
IPO — two heaps on two different keys.

All on the 22 DSA Patterns sheet. If heaps in general are new, start with top K elements.

Frequently asked

How do two heaps find a running median?

A max-heap holds the smaller half of the values and a min-heap holds the larger half. Keep every value in the max-heap at or below every value in the min-heap, and keep their sizes within one of each other. The median is then the max-heap's root, or the average of both roots when the count is even — O(1) to read, O(log n) to insert.

Why push to the max-heap first and then transfer?

It removes every branch. Pushing to low and immediately moving its largest element to high guarantees the new value ends up on the correct side without comparing it to the current median, and it works when either heap is empty. A single size rebalance afterwards restores the invariant.

How do you remove an arbitrary element from a heap?

You cannot do it efficiently — a binary heap supports removing the root, not an arbitrary value. The standard workaround is lazy deletion: record the value in a to-remove map and discard it only when it reaches the root, tracking effective sizes separately. If arbitrary deletion is central, a balanced BST is the better structure.

Two Heaps