templates · Heaps & tries

Two heaps (running median)

  • Numbers arrive one by one and you must report the median after each one
  • You need the middle of a changing collection, not the smallest or the largest
  • Sorting again after every insert would be too slow

Two heaps (median)

the one rule

The invariant

Every number in low is ≤ every number in high, and low has the same size as high or one more.

write it from memory

The template

javajava.util.*
/** Running median of a stream. The low half lives in a max-heap, the high half in a min-heap. */class MedianFinder {    private final PriorityQueue<Integer> low = new PriorityQueue<>(Comparator.reverseOrder()); // max on top    private final PriorityQueue<Integer> high = new PriorityQueue<>();                        // min on top     void add(int x) {        low.offer(x);                                 // always enter through the low half        high.offer(low.poll());                       // its biggest moves up, so low <= high stays true        if (high.size() > low.size()) low.offer(high.poll()); // keep low the same size or one bigger    }     double median() {        if (low.isEmpty()) throw new IllegalStateException("no numbers yet");        if (low.size() > high.size()) return low.peek();       // odd count: middle is low's top        return ((long) low.peek() + high.peek()) / 2.0;        // even: average, long avoids overflow    }}

Enter through low, pass its biggest to high, then move one back if high got bigger. Three lines, and both rules stay true.

fill in the blanks — only these lines change per problem

  1. line 3What the left heap holds. For a median it is the smaller half, kept as a max-heap with Comparator.reverseOrder().
  2. line 9The size rule. For a median: low may be one bigger. Other problems use a different rule: in IPO, every project you can now afford moves from a capital min-heap into a profit max-heap.
  3. line 14What to answer when the count is odd: the top of the bigger heap.
  4. line 15What to answer when the count is even: the average of both tops, done in long or double.

complexity

What it costs

time O(log n) per add, O(1) per median
An add does a constant number of heap offers and polls, each O(log n). The median only peeks at the two tops.
space O(n)
Every number seen so far sits in one of the two heaps.

watch out

Common bugs

  • Forgetting Comparator.reverseOrder(), so both heaps are min-heaps and the median is wrong.
  • Averaging two big ints as (a + b) / 2. It overflows and also does integer division. Use ((long) a + b) / 2.0.
  • Adding straight to one heap without the cross step, so a big number can sit in low and break the order.

use it

Practise it on

learn it properly