Heaps

Two Heaps

Balance a max-heap and a min-heap to track a running median or split point.

Hard, about 90 minutes to practise.

1Understand

The idea

Split the numbers into a lower half (a max-heap) and an upper half (a min-heap), keeping their sizes equal or off by one. The median is then on top of one or both heaps, available in O(1) at all times, and each insertion costs O(log n) plus a rebalance.

Intuition

Split numbers into a lower half (max-heap) and an upper half (min-heap), keeping sizes equal or off by one. The median is then on top of one or both heaps, O(1) read, and each insertion is O(log n) plus a possible rebalance.

In Python, simulate the max-heap with negated values. The invariant: every element in low ≤ every element in high, and size(low) is size(high) or one larger.

This is the standard "median from data stream" structure.

What you will be able to do

  • Maintain size and order invariants
  • Read the median from the tops

When to use it

  • Median of a data stream
  • Balance two halves of the data

2See it

Walkthrough

Median with two heaps

Stream 1, 5, 2, max-heap lows + min-heap highs.

1 / 5

median 1
-1[0] root

lows stores negatives for max-heap. After 1: lows=[-1], highs=[].

heappush(lows, -1)

Live template

1low, high = [], [] # max-heap (negated), min-heap
2def add(x):
3 heapq.heappush(low, -x)
4 heapq.heappush(high, -heapq.heappop(low))
5 if len(high) > len(low): heapq.heappush(low, -heapq.heappop(high))

Complexity: time O(log n) per insert, space O(n)

Each insert O(log n), median O(1), space O(n). Sorting at each step is O(n²) or O(n log n) per query. Two heaps are the intended streaming solution.

Read the walkthrough as text

Running median. Insert 1, then 2, then 3.

  1. Insert 1 into low (max-heap). Median 1.
  2. Insert 2: goes to high; rebalance so low has the extra if needed. Heaps: low=[1], high=[2]. Median (1+2)/2.
  3. Insert 3: to high → high=[2,3]; move 2 to low. low=[2,1], high=[3]. Median 2.

Always push to one heap, then peek/compare and rebalance sizes so the invariant holds.

3Recognise it

Kinds of problems (4)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Median of a stream

    Example. Median after each number is added.

    How. Low half in max-heap (negated), high half in min-heap; rebalance sizes after each insert.

  • Sliding window median (lazy deletion)

    Example. Median of each window of size k.

    How. Same two heaps plus delayed deletes in maps; prune stale tops before reading median.

  • Maximise capital (IPO)

    Example. Pick projects with capital and profit constraints.

    How. Sort by capital; min-heap affordable by capital; pop max profit from max-heap when affordable.

  • Split into two balanced halves

    Example. Partition so low heap holds lower half and high heap the upper.

    How. Stream into low/high with rebalance invariant: low size ≥ high size and low.top ≤ high.top.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Heaps unbalanced

    Why it happens. Medians still “work” if heaps differ by two until you read the wrong top.

    How it fails. len(high) exceeds len(low)+1, median read from empty or wrong half.

    Fix. After each insert, rebalance so size difference is at most 1 (low has equal or one extra).

  • Halves out of order

    Why it happens. Rebalancing sizes without checking order still yields two piles.

    How it fails. max(low)=10, min(high)=8 after moves, halves overlap and median is meaningless.

    Fix. If low.top > high.top, move top from one heap to the other, then fix sizes.

  • Negation forgotten

    Why it happens. Negating on push but not on read feels redundant.

    How it fails. Median from max-heap stored as -3 instead of 3, off by sign and wrong order.

    Fix. Push -x into max-heap; read -heap[0] for the actual largest of the low half.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons