class MedianFinder {
PriorityQueue<Integer> maxHeap;
PriorityQueue<Integer> minHeap;
/** initialize your data structure here. */
public MedianFinder() {
maxHeap = new PriorityQueue<>((a,b) -> b - a);
minHeap = new PriorityQueue<>((a,b) -> a - b);
}
public void addNum(int num) {
if(maxHeap.size() == 0|| num <= maxHeap.peek()){
maxHeap.offer(num);
}else{
minHeap.offer(num);
}
//exchange element because maxHeap must be larger than minHeap.
if (maxHeap.size() > minHeap.size() + 1){
minHeap.add(maxHeap.poll());
}else if (maxHeap.size() < minHeap.size()){
maxHeap.add(minHeap.poll());
}
}
public double findMedian() {
if(maxHeap.size() != minHeap.size()){
return maxHeap.peek();
}else{
return maxHeap.peek() / 2.0 + 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();
*/
