The Middle Ground

How do you find the Median of a continuously growing stream of numbers?

• [2] → Median 2
• [2, 3] → Median 2.5
• [2, 3, 4] → Median 3

Sorting every time is too slow (O(N log N)).

1. The Two Heaps Pattern

Split the data into two halves:

1. Small Half: Max Heap (We need the largest of the smalls).
2. Large Half: Min Heap (We need the smallest of the large).

Median is either the top of one heap or the average of both tops.

2. Interactive: Two Heaps

Add numbers. See them balance.

Max Heap (Small)

Min Heap (Large)

Median: 0

3. Implementation

PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> large = new PriorityQueue<>();

public void addNum(int num) {
  small.offer(num);
  large.offer(small.poll());
  if (large.size() > small.size()) {
    small.offer(large.poll());
  }
}