Q24: How do you find the Median from a Data Stream using Two Heaps?

Maintain two heaps:

maxHeap (Max-Heap): Stores the smaller half of numbers.
minHeap (Min-Heap): Stores the larger half of numbers.

addNum(num): Push to maxHeap. Move maxHeap.poll() to minHeap. If minHeap.size() > maxHeap.size(), move minHeap.poll() back to maxHeap.
findMedian(): If sizes equal, average of tops; otherwise maxHeap.peek().

Two-Heap Median Finder

import java.util.Collections;
import java.util.PriorityQueue;

public class MedianFinder {
    private final PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    private final PriorityQueue<Integer> 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;
    }
}

💡 Balances two heap structures to retrieve stream medians in $O(1)$ time.

Key Takeaways

Max-Heap (small half) + Min-Heap (large half).
addNum: $O(log n)$ time; findMedian: $O(1)$ time.

Knowledge Check

What is the time complexity of the findMedian() method in the Two-Heap approach?

Q24: How do you find the Median from a Data Stream using Two Heaps?

STAY UPDATED WITH BYTES!