LeetCode : 295. Find Median from Data Stream

[congr]

https://leetcode.com/problems/find-median-from-data-stream/

[congr]

class MedianFinder {
    PriorityQueue<Integer> minHeap, maxHeap;

    /** initialize your data structure here. */
    public MedianFinder() {
        minHeap = new PriorityQueue();
        maxHeap = new PriorityQueue(Collections.reverseOrder());
    }

    public void addNum(int num) {
        if (num < findMedian()) maxHeap.add(num);
        else minHeap.add(num);

        rebalance();
    }

    void rebalance() {
        if (Math.abs(minHeap.size() - maxHeap.size()) <= 1) return;

        if (minHeap.size() > maxHeap.size()) maxHeap.add(minHeap.remove());
        else minHeap.add(maxHeap.remove());
    }

    public double findMedian() {
        int minHeapSize = minHeap.size(), maxHeapSize = maxHeap.size();

        if (minHeapSize == 0 && maxHeapSize == 0) return 0; // !!! at first

        if (minHeapSize == maxHeapSize) 
            return ((double)minHeap.peek() + maxHeap.peek()) / 2;
        else if (minHeapSize > maxHeapSize) return minHeap.peek();
        else return maxHeap.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */