如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
import java.util.Collections;
import java.util.PriorityQueue;
public class Solution {
// smaller堆用于存放相对较小的一半数字，larger堆用于存放相对较大的一半数字
// 由于默认排序堆顶是最小值，而对于smaller的一半我们更关注最大值，因此使用reverseOrder()来初始化
private PriorityQueue<Integer> smaller = new PriorityQueue<>(Collections.reverseOrder());
private PriorityQueue<Integer> larger = new PriorityQueue<>();
public void Insert(Integer num) {
// 首次将数字存入smaller，然后在将smaller中堆顶的（较小一半数字的最大值）存入larger
smaller.add(num);
larger.add(smaller.poll());
// 为了保证larger内的数量<=smaller内的数量，进行两个堆大小的比较，并进行转移
// 此规则下，如果两个堆数量相等，则中位数为两个堆顶数字的平均值；若不相等则为smaller的堆顶数字
// 也可以使larger存储更多数字，则不相等时，中位数为larger的堆顶数字
if (larger.size() > smaller.size()) {
smaller.add(larger.poll());
}
}
public Double GetMedian() {
// 如前所述，两者大小相等，则求平均
if (smaller.size() == larger.size()) {
return ((double)smaller.peek() + (double)larger.peek()) / 2;
} else { // 否则中位数为smaller的堆顶数字
return (double)smaller.peek();
}
}
}题目描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
解题思路 先用java集合PriorityQueue来设置一个小顶堆和大顶堆 主要的思想是：因为要求的是中位数，那么这两个堆，大顶堆用来存较小的数，从大到小排列； 小顶堆存较大的数，从小到大的顺序排序*，显然中位数就是大顶堆的根节点与小顶堆的根节点和的平均数。 ⭐保证：小顶堆中的元素都大于等于大顶堆中的元素，所以每次塞值，并不是直接塞进去，而是从另一个堆中poll出一个最大（最小）的塞值 ⭐当数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中； ⭐当数目为奇数的时候，将这个值插入小顶堆中，再讲小顶堆中根节点（即最小值）插入到大顶堆中； ⭐取中位数的时候，如果当前个数为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当前个数为奇数，显然是取小顶堆的根节点 理解了上面所述的主体思想，下面举个例子辅助验证一下。
例如，传入的数据为：[5,2,3,4,1,6,7,0,8],那么按照要求，输出是"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
那么整个程序的执行流程应该是（用min表示小顶堆，max表示大顶堆）：
5先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[5],max=[无]，avg=[5.00] 2先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[5],max=[2],avg=[(5+2)/2]=[3.50] 3先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[3,5],max=[2],avg=[3.00] 4先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[4,5],max=[3,2],avg=[(4+3)/2]=[3.50] 1先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[3,4,5],max=[2,1]，avg=[3/00] 6先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[4,5,6],max=[3,2,1],avg=[(4+3)/2]=[3.50] 7先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[4,5,6,7],max=[3,2,1],avg=[4]=[4.00] 0先进入小顶堆，然后将小顶堆中最大值放入小顶堆中，此时min=[4,5,6,7],max=[3,2,1,0],avg=[(4+3)/2]=[3.50] 8先进入大顶堆，然后将大顶堆中最小值放入大顶堆中，此时min=[4,5,6,7,8],max=[3,2,1,0],avg=[4.00]