面试题：数据流中的中位数
题目：
如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值
思路：
书上给出了几种思路，简单叙述一下，因为没有敲代码，就不涉及细节啦
1）用数组来存放数据。没有排序的数组则用partition方法（快排中放置元素的方法）
2）用排序的链表来存放数据
3）二叉搜索树
4）平衡的二叉搜索树
使用的方法：
由于中位数（一个或两个数的平均值）将排序的数据流分为两个部分，设排序从小到大，则中位数左边部分的所有数都小于中位数的右边部分，如下图：
将数据流从中位数截断的两部分用两个容器来放置：
中位数左边，偏小部分，用最大堆保存数据——便于查找该堆中的最大数；
中位数右边，偏大部分，用最小堆保存数据——便于查找该堆中的最小数；
因为需要中位数左边和右边的部分应相同（或最多差一个数），则在两个部分交替放置数。
此处设count记录交替，偶数时放左边（最大堆），奇数时放右边（最小堆）
因此，当在数组（总）长度为偶时，若需要中位数，则此时中位数为最大堆中的最大值和最小堆中的最小值的平均值；若数组（总）长度为奇时，若需要中位数，则此时中位数在最小堆中
【需要注意的点】
当要往最大堆（较小部分）插入的数，比最小堆（较大部分）的顶部元素还大时，说明该数比较大部分的一部分数要更大，但左、右两部分应保持【左边的所有元素都比右边的元素更小】，因此，先将这个数插入到最小堆中（会自动进行堆调整，并将当前最小堆中最小的元素放到顶部），再取出最小堆中的顶部元素（此时较大部分中的最小数），插入到最大堆中，这样能保证右边的数依旧比左边的数更大（交换过去的数是右边部分最小的数）
当要往最小堆（较大）部分插入的数，比最大堆（较小部分）的顶部元素还小时，同理。
【具体】
使用PriorityQueue来构造两个容器，默认内部是自然排序，结果为最小堆，也可以自定义排序器（在new的时候传入一个comparator可得到最大堆）
PriorityQueue的一些操作区别：https://www.cnblogs.com/Elliott-Su-Faith-change-our-life/p/7472265.html
【代码】
// 2019-06-25 public static int getMiddle(int[] a) { if(a.length==0) { System.out.println("wrong input"); return 0; } mHeap myHeap = new mHeap(); int count = 1; myHeap.maxHeap.offer(a[0]); for(int i=1;i<a.length;i++) { // 奇左 if(count%2==0) { int t = myHeap.minHeap.peek(); if(a[i]>t) { myHeap.minHeap.offer(a[i]); t = myHeap.minHeap.poll(); myHeap.maxHeap.offer(t); }else { myHeap.maxHeap.offer(a[i]); } // 偶右 }else { int t = myHeap.maxHeap.peek(); if(a[i]<t) { myHeap.maxHeap.offer(a[i]); t = myHeap.maxHeap.poll(); myHeap.minHeap.offer(t); }else { myHeap.minHeap.offer(a[i]); } } count++; } // 得到中位数 if(count%2==1) { return myHeap.maxHeap.peek(); }else { return (myHeap.maxHeap.peek() + myHeap.minHeap.peek())/2; } } // 自定义类 public class mHeap { PriorityQueue<Integer> minHeap; PriorityQueue<Integer> maxHeap; int count; public mHeap() { minHeap = new PriorityQueue<Integer>(); maxHeap = new PriorityQueue<Integer>(15,new Comparator<Integer>() { public int compare(Integer x1,Integer x2) { return x2-x1; } }); count=0; } } // 主函数及功能函数代码 public class Q41 { public static void main(String[] args) { mHeap myHeap = new mHeap(); Scanner sc = new Scanner(System.in); while(sc.hasNextInt() ) { int flag = sc.nextInt(); if(flag==-1) { showMiddle(myHeap); myHeap = new mHeap(); }else { updateHeap(myHeap,flag); } } } // 得到中位数 public static double showMiddle(mHeap heap) { double x =0; // 如果最大堆和最小堆都为空 if(heap.count==0) { System.out.println("null heap"); return x; } // 不为空，则偶数输出平均值，奇数输出最小堆的数 if(heap.count%2==0) { x = (double)(heap.maxHeap.peek()+heap.minHeap.peek())/2; }else { x = heap.minHeap.peek(); } System.out.printf("middle:%f",x); return x; } // 插入新的数据 public static void updateHeap(mHeap heap,int x) { heap.count++; // 偶左——放入最大堆中 if(heap.count%2==0) { // 如果要插入的数大于右边某些数（大于最小堆最小值） // 则把最大堆中的最小值放入到最小堆中，将要插入的值放入到最大堆之中 if(!heap.minHeap.isEmpty() && x>heap.minHeap.peek()) { heap.minHeap.offer(x); x = heap.minHeap.poll(); } heap.maxHeap.offer(x); // 奇右——放入最小堆中 }else { if(!heap.maxHeap.isEmpty() && x<heap.maxHeap.peek()) { heap.maxHeap.offer(x); x = heap.maxHeap.poll(); } heap.minHeap.offer(x); } } }
