⚖️

Two Heaps — Running Median

Keep a LO max-heap (lower half) and HI min-heap (upper half), always balanced within 1. After each insert, lo.peek() and hi.peek() give the median in O(1).

⚖️ Balance Invariant 📊 O(1) Median Query 🔃 Streaming Data addNum O(log n) findMedian O(1) Space O(n)

📋 When to Use

Running median — median changes as new numbers arrive
Two halves invariant — lo holds ≤ half, hi holds > half; |lo.size - hi.size| ≤ 1
Balance rule — always add to lo first, then move lo.top→hi; if lo smaller, move hi.top→lo
O(1) query — median = lo.peek() (odd total) or avg of both tops (even)

💡 Key insight: LO always has ≥ HI in size, so lo.peek() is always the median (or one of the two middle elements). Never query the full heaps — just the tops!

⚡ Complexity

addNum

O(log n)

findMedian

O(1)

Each insertion does at most 2 heap operations (offer+poll) → O(log n).
Total space: O(n) — each element is in exactly one heap.
Compare: sorting after each insert = O(n²), order-statistics tree = O(log n) but complex.
Two heaps: simple, fast, standard interview approach.

Problem Design a data structure supporting addNum and findMedian. Insert stream = [5,15,1,3,8,7,9,25,10,6] one by one and report the running median after each insertion. Use a LO max-heap (lower half) + HI min-heap (upper half), kept balanced within 1 element.
Input: stream = [5,15,1,3,8,7,9,25,10,6] · Answer: final median = 7.5 (sorted: [1,3,5,6,7,8,9,10,15,25])

Step 0 / 11

⚖️ Init ➕ Add → LO → Move to HI ← Rebalance 📊 Median

📡 Input Stream

LO size0

HI size0

Median—

🔻

LO — Max-Heap

Lower half · max at top

empty

Balance

→ HI

📊 Median

—

← LO

🔺

HI — Min-Heap

Upper half · min at top

empty

⚖️ Two Heaps: LO (max-heap) holds lower half, HI (min-heap) holds upper half. Stream numbers in, get the median any time in O(1)!

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

🧩 Pattern Skeleton Java 8

// Two Heaps — Running Median ─────────────────────────────────
PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
PriorityQueue<Integer> hi = new PriorityQueue<>();                               // min-heap

void addNum(int num) {
    lo.offer(num);                        // step 1: always add to lo
    hi.offer(lo.poll());                  // step 2: move lo's max to hi
    if (lo.size() < hi.size())            // step 3: rebalance if needed
        lo.offer(hi.poll());
}

double findMedian() {
    return lo.size() > hi.size()
        ? lo.peek()                       // odd total: lo has the middle
        : (lo.peek() + hi.peek()) / 2.0; // even: average of two middles
}

🎯 Practice Problems

#295 Find Median from Data Stream ⚖️ two heaps Hard #480 Sliding Window Median ⚖️ two heaps + lazy delete Hard #502 IPO 💰 max capital with two heaps Hard #253 Meeting Rooms II 📅 min-heap on end times Medium #621 Task Scheduler ⏰ greedy + max-heap freq Medium