Find Median from Data Stream
Description
Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
Examples: [2,3,4] , the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5
Design a data structure that supports the following two operations:
void addNum(int num) - Add a integer number from the data stream to the data structure. double findMedian() - Return the median of all elements so far. For example:
add(1) add(2) findMedian() -> 1.5 add(3) findMedian() -> 2
Hint
Train of Thought
The basic idea is to maintain two heaps: a max-heap and a min-heap. The max heap stores the smaller half of all numbers while the min heap stores the larger half. The sizes of two heaps need to be balanced each time when a new number is inserted so that their size will not be different by more than 1. Therefore each time when findMedian() is called we check if two heaps have the same size. If they do, we should return the average of the two top values of heaps. Otherwise we return the top of the heap which has one more element.
Code
private PriorityQueue<Integer> minH;
private PriorityQueue<Integer> maxH;
MedianFinder(){
minH = new PriorityQueue<Integer>();
maxH = new PriorityQueue<Integer>(1, new Comparator<Integer>(){
public int compare(Integer o1, Integer o2) {
if (o1.intValue()>o2.intValue()) return -1;
if (o1.intValue()<o2.intValue()) return 1;
return 0;
}
});
}
public void addNum(int num) {
if ((minH.size()==0)&&(maxH.size()==0)) minH.add(num);
else if ((minH.size())>(maxH.size())) {
if (num>minH.peek()) {
maxH.add(minH.poll());
minH.add(num);
} else maxH.add(num);
} else if ((minH.size())<(maxH.size())) {
if (num<maxH.peek()) {
minH.add(maxH.poll());
maxH.add(num);
} else minH.add(num);
} else {
if (num<maxH.peek()) maxH.add(num);
else minH.add(num);
}
}