CodeWithYash

Intermediate · Module 14 · Lesson 4

Two heaps

Balance lower and upper halves for streaming medians.

15–25 min readLesson 80 of 123

Lesson 80 of 123

1d streak

The Two-Heaps Pattern: Dynamic Streaming Median in O(1)

Finding the median of a dynamic stream of numbers where elements arrive continuously is solved with the Two Heaps Pattern: partition numbers into a lower half and an upper half.

Two Heaps Balancing Invariant
Lower Half (Smaller numbers)      Upper Half (Larger numbers)
+-------------------------------+ +-------------------------------+
| MAX-HEAP                      | | MIN-HEAP                      |
| [ 1, 3, 5 ]    Root = 5       | | [ 7, 9, 11 ]   Root = 7       |
+-------------------------------+ +-------------------------------+

Invariants:
1. Every element in maxHeap <= every element in minHeap.
2. Sizes differ by at most 1 (maxHeap holds extra element if total count is odd).

Median Calculation in O(1):
- Odd total elements:  median = maxHeap.peek()
- Even total elements: median = (maxHeap.peek() + minHeap.peek()) / 2.0
MedianFinder.java
class MedianFinder {
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll()); // Balance values

        // Maintain size invariant: maxHeap size >= minHeap size
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

Cost Model

Complexity & Trade-offs

Insert / median
O(log n) / O(1)
O(n)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Top-k, streaming medians, scheduling, and best-first frontiers.
  • Repeated access to an extreme without fully sorting.
  • Merging sorted sources.

Common mistakes

  • Choosing the wrong heap direction for a bounded top-k set.
  • Assuming heap iteration is globally sorted.
  • Claiming bottom-up heap construction is O(n log n).

Practice prompts

  • Reproduce the worked Two heaps example without looking at the trace.
  • Change one input condition and explain whether the Two heaps invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.