59、数据流中的中位数

题目

如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路

1、如果数据流中的数据个数为偶数，那么中位数可以用p1和p2表示，指向不同的但是相邻的中间数据
- p1指针之前的数据流中特点：p1数值为最大的值
- p2指针之前的数据流特点：p2数值为最小的值
- 不需要左右两个数据流是按照排序的，只需要知道左边数据流中的最大值、并且左边数据流中的数据值全部小于右边数据流中的所有值
2、如果数据流中的数据个数为奇数，那么中位数可以用p1和p2表示，指向数据流中间数据同一个数据，两个指针重合
- p1指针之前的数据流中特点：p1数值为最大的值
- p2指针之前的数据流特点：p2数值为最小的值
- 不需要左右两个数据流是按照排序的，只需要知道左边数据流中的最大值、并且左边数据流中的数据值全部小于右边数据流中的所有值
3、能够确定数据流中最大值、最小值的数据结构是最大堆和最小堆数据结构
最大堆和最小堆数据结构的特点：
- 堆顶的数据是最大、最小值
- 父节点的数值大于或者等于、小于或者等于子节点数值
- 并且数据之间没有顺序之分
4、怎么使用最大堆、最小堆数据结构解决本题目？
- 当数据流中数据个数为偶数，首先将新数据放入最小堆中
- 如果新数据的值小于最大堆的其中一些数值，那么将新数据值放入到最大堆中，并且将重新排好序的最大堆的堆顶数值写入到最小堆，然后最小堆排序，这样就保证最大堆数据值都小于最小堆的值
- 当数据流中数据个数为奇数，首先将新数据放入最大堆中
- 如果新数据的值大于最小堆其中一些数据值，那么将新数据值放入到最小堆中，并且将重新排好序的最小堆的最小数值写入到最大堆，然后最大堆排序，这样就保证最大堆数据值都小于最小堆的值

代码

import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    int count =0;
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(15,new Comparator<Integer>(){
        public int compare(Integer o1,Integer o2){
            return o2.compareTo(o1);
        }
    });
    public void Insert(Integer num) {
        if(count%2==0){
        //偶数时，将新数据放到最大堆，然后取出最大堆的最大值放到最小堆，这样可以免除可能出现新数据小于最大堆其中数据值的情况
        //新数据就停留在最大堆中了
        //奇数时候的情况类似
            maxHeap.offer(num);
            int topmaxHeap = maxHeap.poll();
            minHeap.offer(topmaxHeap);
        }else{
            minHeap.offer(num);
            int topminHeap = minHeap.poll();
            maxHeap.offer(topminHeap);
        }
        count++;
    }

    public Double GetMedian() {
        if(count%2==0){
            return new Double((minHeap.peek()+maxHeap.peek())) /2;
        }else
            return new Double(minHeap.peek());
    }


}