295. Find Median from Data Stream - pangeneral/leetcode-notebook GitHub Wiki

Use two heaps leftQueue and rightQueue save the maximum element in the left part of data stream and minimum element in the right part of data stream respectively. Update the two heaps so that rightQueue.size() = leftQueue.size() or rightQueue.size() = leftQueue.size() + 1.

class MedianFinder {
    
    PriorityQueue<Integer> leftQueue = new PriorityQueue<Integer>(Collections.reverseOrder());
    PriorityQueue<Integer> rightQueue = new PriorityQueue<Integer>();
    
    /** initialize your data structure here. */
    public MedianFinder() {
    }
    
    public void addNum(int num) {
        rightQueue.offer(num);
        leftQueue.offer(rightQueue.poll());
        if( rightQueue.size() < leftQueue.size())
            rightQueue.offer(leftQueue.poll());
    }
    
    public double findMedian() {
        if( rightQueue.size() == 0 )
            return 0;
        else if( leftQueue.size() == rightQueue.size() )
            return ((double) leftQueue.peek() + rightQueue.peek()) / 2;
        else
            return rightQueue.peek();
    }
}
⚠️ **GitHub.com Fallback** ⚠️