Pattern 10: Two Heaps

0. The Template (Copy-Paste Skeleton)

A max-heap of the smaller half and a min-heap of the larger half, kept balanced. The two heap tops straddle the median, so the median is O(1).

// TEMPLATE — RUNNING MEDIAN (LC 295)
class MedianFinder {
    // lo = max-heap over the SMALLER half  → its top is the largest of the small ones
    private final PriorityQueue<Integer> lo = new PriorityQueue<>(Comparator.reverseOrder());
    // hi = min-heap over the LARGER  half  → its top is the smallest of the large ones
    private final PriorityQueue<Integer> hi = new PriorityQueue<>();

    public void addNum(int num) {
        lo.offer(num);              // 1. always push into lo first
        hi.offer(lo.poll());        // 2. move lo's max across → guarantees every lo ≤ every hi
        if (hi.size() > lo.size())  // 3. rebalance: lo may hold one extra, hi may not
            lo.offer(hi.poll());
    }

    public double findMedian() {
        return lo.size() > hi.size()
            ? lo.peek()                                  // odd count → lo holds the extra
            : (lo.peek() + hi.peek()) / 2.0;             // even → average the two tops
    }
}

The invariants — state them, then the code writes itself

1. max(lo) <= min(hi) — every element in lo is ≤ every element in hi.
2. lo.size() == hi.size() or lo.size() == hi.size() + 1 — lo may hold one extra.

Why push-then-transfer-then-rebalance (3 lines, no if-chain)

Pushing into lo and immediately moving lo’s max into hi enforces invariant 1 unconditionally — you never have to compare num against the tops. The single rebalance line then restores invariant 2. Three lines, no branching on value. Compare that with the “if (num <= lo.peek()) … else …” version, which needs four cases and is where people lose the interview.

Java specifics

Need	Code
min-heap (default)	new PriorityQueue<>()
max-heap	new PriorityQueue<>(Comparator.reverseOrder())
max-heap (older style)	new PriorityQueue<>((a, b) -> Integer.compare(b, a)) — never b - a (overflow)
heap of objects	new PriorityQueue<>(Comparator.comparingInt(o -> o.field))
integer overflow on the average	(lo.peek() + hi.peek()) / 2.0 overflows int at 2×10^9 — cast: ((long) lo.peek() + hi.peek()) / 2.0
build from a collection	new PriorityQueue<>(list) is O(n) heapify, not O(n log n)

PriorityQueue.remove(Object) is O(n) — it scans. For sliding-window medians (LC 480) use lazy deletion with a HashMap of pending removals, or switch to a TreeMap.

When two heaps is the answer

• Running / streaming median
• “Schedule the next job by earliest end time” while also tracking the largest profit (LC 502)
• IPO / capital problems — one heap ordered by cost, another by profit
• Sliding-window median (LC 480) — two heaps plus lazy deletion

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Find the median” from a data stream
• “Schedule” or “assign” tasks with constraints
• Need to efficiently track both the “smaller half” and “larger half” of data
• “K-th largest/smallest” in a stream
• Problems where you need quick access to the middle of sorted data

The Algorithm (Pseudocode)

maxHeap = new MaxHeap()   // stores the SMALLER half
minHeap = new MinHeap()   // stores the LARGER half

addNum(num):
    maxHeap.add(num)

    // Balance: ensure maxHeap's max <= minHeap's min
    minHeap.add(maxHeap.poll())

    // Keep sizes balanced (maxHeap can have at most 1 extra)
    if minHeap.size() > maxHeap.size():
        maxHeap.add(minHeap.poll())

findMedian():
    if maxHeap.size() > minHeap.size():
        return maxHeap.peek()
    else:
        return (maxHeap.peek() + minHeap.peek()) / 2.0

The ‘Trick’ to Know

• The maxHeap holds the smaller half, so its top is the “largest of the small numbers.” The minHeap holds the larger half, so its top is the “smallest of the large numbers.” The median is always at these two tops.
• Always add to maxHeap first, then rebalance. This ensures the invariant is maintained in O(log n).

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Find Median from Data Stream - LC 295

Brute Force: Sort on Every Query - O(n log n) per findMedian

class MedianFinder {
    private List<Integer> data;

    public MedianFinder() {
        data = new ArrayList<>();
    }

    public void addNum(int num) {
        data.add(num);
    }

    public double findMedian() {
        Collections.sort(data);
        int n = data.size();
        if (n % 2 == 1) return data.get(n / 2);
        return (data.get(n / 2 - 1) + data.get(n / 2)) / 2.0;
    }
}

Optimal: Two Heaps - O(log n) per add, O(1) per findMedian

class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // smaller half
    private PriorityQueue<Integer> minHeap; // larger half

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

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

        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;
    }
}

Java Architecture Insights

• PriorityQueue is a min-heap by default: For a max-heap, use Collections.reverseOrder() or (a, b) -> b - a (but avoid subtraction for overflow safety).
• offer() vs add(): Functionally identical for unbounded PriorityQueue. offer() is the Queue-interface method.
• Why not TreeMap? TreeMap gives O(log n) for everything but is overkill. PriorityQueue is simpler and has lower constant factor.

---

3. Mental Model & Visualization

ASCII Diagram (Stream: 5, 15, 1, 3)

Add 5:  maxHeap=[5]      minHeap=[]         median=5
Add 15: maxHeap=[5]      minHeap=[15]       median=(5+15)/2=10
Add 1:  maxHeap=[5,1]    minHeap=[15]       
        → rebalance: maxHeap=[5,1] minHeap=[15]  median=5
Add 3:  maxHeap=[3,1]    minHeap=[5,15]     median=(3+5)/2=4

maxHeap (top = largest of small):  [3, 1]
minHeap (top = smallest of large): [5, 15]

Senior Mental Trigger

“Median or ‘middle’ of a stream = two heaps: maxHeap for small half, minHeap for large half.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 295	Find Median from Data Stream	Hard
LC 703	Kth Largest Element in a Stream	Easy
LC 1046	Last Stone Weight	Easy
LC 215	Kth Largest Element in an Array	Medium
LC 373	Find K Pairs with Smallest Sums	Medium

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 480	Sliding Window Median	Hard
LC 502	IPO	Hard
LC 436	Find Right Interval	Medium
LC 253	Meeting Rooms II	Medium
LC 621	Task Scheduler	Medium

---

5. Time & Space Complexity Table

Approach	addNum	findMedian	Space	Notes
Sort each time	O(n log n)	O(1)	O(n)	Re-sort on every query
Insertion Sort	O(n)	O(1)	O(n)	Binary search + shift
Two Heaps	O(log n)	O(1)	O(n)	Optimal for streaming