Thinking process - Double Heap
Use a maxHeap to save smaller half of current input
Use a minHeap to save larger half of current input
Update two heap when a new integer added
Output
- if even, then the median is (max in maxHeap + min in minHeap) / 2
- if odd, then the min in minHeap
Time Complexity
O (logn) + O (1)
Mistakes
don't forget the cases that max in maxHeap might larger than min in minHeap
public class MedianFinder {
PriorityQueue<Integer> minHeap;
PriorityQueue<Integer> maxHeap;
/** initialize your data structure here. */
public MedianFinder() {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<>(1, new Comparator<Integer>(){
public int compare(Integer a, Integer b) {
return (a - b) > 0 ? -1 : 1;
}
});
}
public void addNum(int num) {
minHeap.add(num);
if (minHeap.size() - 1 > maxHeap.size()) {
maxHeap.add(minHeap.poll());
} else {
if (!maxHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
minHeap.add(maxHeap.poll());
maxHeap.add(minHeap.poll());
}
}
}
public double findMedian() {
if (minHeap.size() != maxHeap.size()) {
return (double)minHeap.peek();
} else {
double result = (minHeap.peek() + maxHeap.peek()) / 2.0;
return result;
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/