# 295 Find Median from Data Stream

• Idea:

  1. Use 2 PQ, maxheap for the smaller half, minheap for the larger half.
  2. addNum(): find out if num is the smaller half or larger half put num into maxheap. then take the top one in maxheap to minheap if minheap > maxheap, take the top one in minheap to maxheap.
  3. findMedian(): if minheap.size != max heap.size(), get the top one of the larger heap. otherwise, get the top one of both heaps and divide by 2

• Code:

public class MedianFinder {
    PriorityQueue<Integer> maxheap;
    PriorityQueue<Integer> minheap;

    /** initialize your data structure here. */
    public MedianFinder() {
        maxheap = new PriorityQueue(1000, Collections.reverseOrder());
        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();
        }else if(maxheap.size() < minheap.size()){
            return minheap.peek();
        }else{
            return (maxheap.peek()+minheap.peek())/2.0;
        }
    }
}

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