Find Median from Data Stream

1class MedianFinder {
2    // Max heap for lower half
3    private PriorityQueue<Integer> maxHeap;
4    // Min heap for upper half
5    private PriorityQueue<Integer> minHeap;
6
7    public MedianFinder() {
8        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
9        minHeap = new PriorityQueue<>();
10    }
11
12    public void addNum(int num) {
13        // Add to appropriate heap
14        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
15            maxHeap.offer(num);
16        } else {
17            minHeap.offer(num);
18        }
19
20        // Balance heaps
21        if (maxHeap.size() > minHeap.size() + 1) {
22            minHeap.offer(maxHeap.poll());
23        } else if (minHeap.size() > maxHeap.size()) {
24            maxHeap.offer(minHeap.poll());
25        }
26    }
27
28    public double findMedian() {
29        if (maxHeap.size() > minHeap.size()) {
30            return maxHeap.peek();
31        }
32        return (maxHeap.peek() + minHeap.peek()) / 2.0;
33    }
34}