import java.util.*;
public class Solution {
    //较大值构成小顶堆
    PriorityQueue<Integer> max = new PriorityQueue<>((o1,o2)->o1.compareTo(o2));
    //较小值构成大顶堆
    PriorityQueue<Integer> min = new PriorityQueue<>((o1,o2)->o2.compareTo(o1));
    public void Insert(Integer num) {
        min.offer(num);
        max.offer(min.poll());
        //平衡两个堆的数量
        if(min.size()<max.size()){
            min.offer(max.poll());
        }
    }

    public Double GetMedian() {
        //奇数个取最中间的值，我们约定放在大根堆
        if(min.size() > max.size()){
            return (double)min.peek();
        }else{
            //偶数个，取中间两个的平均值
            return (double)(min.peek()+max.peek())/2;
        }
    }
}

方法一：堆排序

取中位数要看数据个数的奇偶数，所以我们可以把数据分为两部分，较大的采用小根堆存储，较小的采用大根堆存储，这样通过取两个的堆顶就可以得到中间的两个数进而取得中位数。

具体步骤：

1、定义两个堆，分别存储较大值和较小值

2、数据流入部分，我们规定先存储到大根堆进行排序，然后将其最大值弹出赋值给小根堆排序，但是大根堆的个数不能比小根堆少，所以需要比较二者的个数，若大根堆个数少了则将小根堆的堆顶值弹出给大根堆。

，，我们可以规定先存储到大根堆。这样二者个数要么相等，要么大根堆多一

3、取中位数部分，比较两个堆的个数，奇数个数时即大根堆多一个，返回大根堆的堆顶；个数相等即为偶数个数时，将二者堆顶取出求平均值即可。

方法二：插入排序

由于数据流是不断地进来数据的，每输入一个数就要进行一次排序，而前面的数是有序的，所以可以考虑用插入排序。

步骤：

1、声明一个数列用于存储数据流

2、在insert中遍历数组，按递增顺序，插入到最后一个小于它的元素之后。

3、在求中位数时，利用元素个数判断奇偶，通过下标找到中间的数，进而求中位数

import java.util.*;
public class Solution {
    private ArrayList<Integer> arr = new ArrayList<Integer>();
    public void Insert(Integer num) {
        if(arr.isEmpty()){
            arr.add(num);
        }else{
            int i=0;
            for(;i<arr.size();++i){
			  //找到插入的位置
                if(num <= arr.get(i)){
                    break;
                }
            }
		  //在对应位置插入元素 
            arr.add(i,num);
        }
    }

    public Double GetMedian() {
        int n = arr.size();
        if(n%2==0){
            double a = arr.get(n/2);
            double b = arr.get(n/2-1);
            return (a+b)/2.0;
        }else{
            return (double)arr.get(n/2);
        }
    }


}