Continuous Median: Track Streaming Median via Dual Heaps (CTCI 17.20)

TL;DR

• The Problem: CTCI problem 17.20 technical mechanics.
• The Approach: CTCI problem 17.20: track and maintain the median of a numerical data stream using a Max-Heap and Min-Heap.
• Complexity: Optimal Time and Memory bounds.

This article provides a clear breakdown of CTCI problem 17.20.

1. Context and Problem Statement

CTCI problem 17.20: track and maintain the median of a numerical data stream using a Max-Heap and Min-Heap.

2. Technical Code & Mechanics

public class ContinuousMedian {
    private final PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Left lower half
    private final PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // Right upper half
    public void insert(int num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) maxHeap.offer(num);
        else minHeap.offer(num);
        if (maxHeap.size() > minHeap.size() + 1) minHeap.offer(maxHeap.poll());
        else if (minHeap.size() > maxHeap.size()) maxHeap.offer(minHeap.poll());
    }
    public double getMedian() {
        if (maxHeap.size() == minHeap.size()) return (maxHeap.peek() + minHeap.peek()) / 2.0;
        return maxHeap.peek();
    }
}

3. Key Takeaways and Edge Cases

Always test boundary conditions and invalid input states.