数据流中的中位数

这题看到大部分人都是使用大顶堆和小顶堆实现，但是java里面有一个更好的数据结构TreeMap可以帮我们实现排序的功能。这样找中位数就很简单了。算法本身实质是使用hashmap实现桶排序的方法，相比使用堆的方法，当数据重复量大时节省了存储空间，理解起来也很容易。代码如下：

    TreeMap treeMap = new TreeMap<Integer,Integer>();
    public void Insert(Integer num) {
        if(treeMap.containsKey(num)) {
            int sum = (Integer) treeMap.get(num);
            treeMap.replace(num, sum, sum + 1);
        }else {
            treeMap.put(num,1);
        }
    }

    public Double GetMedian() {
        int size = treeMap.size();
        Map.Entry entry = treeMap.firstEntry();
        int i = (int)entry.getValue();
        int mid = (size+1)/2;
        while(i < mid){
            entry = treeMap.higherEntry(entry.getKey());
            i += (int)entry.getValue();
        }
        if(size % 2 == 0 && i == mid){
                return ((int)entry.getKey() * 1.0 + (int)treeMap.higherEntry(entry.getKey()).getKey() * 1.0) / 2;
        }
        return (int)entry.getKey() * 1.0;
    }