Find Median from Data Stream

Problem

Implement MedianFinder: addNum and findMedian. The median is the middle value in sorted order.

Key insight (Two Heaps):

lo: max-heap (lower half, root = max of lower)
hi: min-heap (upper half, root = min of upper)
Maintain: len(lo) == len(hi) or len(lo) == len(hi) + 1

Solutions

// C++
class MedianFinder {
    priority_queue<int> lo;
    priority_queue<int, vector<int>, greater<int>> hi;
public:
    void addNum(int num) {
        lo.push(num);
        hi.push(lo.top()); lo.pop();
        if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }
    }
    double findMedian() {
        return lo.size() > hi.size() ? lo.top() : (lo.top() + hi.top()) / 2.0;
    }
};

// Java
class MedianFinder {
    PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> hi = new PriorityQueue<>();
    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());
        if (hi.size() > lo.size()) lo.offer(hi.poll());
    }
    public double findMedian() {
        return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
    }
}

// JavaScript (MinHeap class assumed)
class MedianFinder {
    constructor() { this.lo = new MaxHeap(); this.hi = new MinHeap(); }
    addNum(num) {
        this.lo.push(num);
        this.hi.push(this.lo.pop());
        if (this.hi.size() > this.lo.size()) this.lo.push(this.hi.pop());
    }
    findMedian() {
        return this.lo.size() > this.hi.size() ? this.lo.peek() : (this.lo.peek() + this.hi.peek()) / 2;
    }
}

# Python
import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (negate)
        self.hi = []  # min-heap

    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Complexity

addNum: O(log n)
findMedian: O(1)

Key Insight

The two heaps form a "split" at the median. After each insertion, rebalance so lo is never smaller than hi, and their sizes differ by at most 1.

Variant: Add lazy deletion for sliding window median (use heap with tombstone set).