题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
题解
将所有数据分为两半，分别放入一个最大堆和一个最小堆中。最大堆用来存较小的数，最小堆用来存较大的数。这时候中位数就是最大堆的根节点和最小根的根节点的平均数。
这种方法一个最关键的点是：在每次插入数据时，不能直接插入，而是需要取另一个堆的根节点进行插入。这样，每次插入最小堆的是当前最大堆中最大的元素，每次插入最大堆的是当前最小堆中最小的元素，这样才能保证最大堆中的值全部小于最小堆中的值。
PriorityQueue<Integer> minHeap;
PriorityQueue<Integer> maxHeap;
Solution() {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
}
public void Insert(Integer num) {
if (minHeap.size() == maxHeap.size()) {
minHeap.offer(num);
if (!minHeap.isEmpty()) maxHeap.offer(minHeap.poll());
}
else {
maxHeap.offer(num);
if (!maxHeap.isEmpty()) minHeap.offer(maxHeap.poll());
}
}
public Double GetMedian() {
if (minHeap.isEmpty() && maxHeap.isEmpty())
return 0.0;
if (!minHeap.isEmpty() && !maxHeap.isEmpty() && minHeap.size() == maxHeap.size())
return (double) (minHeap.peek() + maxHeap.peek()) / 2;
else if (!maxHeap.isEmpty())
return (double) maxHeap.peek();
else return 0.0;
}
