中位数_牛客博客

 
// 大顶端：最大的元素在第一个 PriorityQueue<Integer> heapBig = new PriorityQueue<>(Comparator.reverseOrder()); // 把comparable取反
// 小顶堆：自然序，最小的元素在第一个 PriorityQueue<Integer> heapSmall = new PriorityQueue<>(); 


public void Insert(Integer num) {
            count++;
            heapBig.add(num);
            if (heapBig.size() > heapSmall.size() + 1) {
                heapSmall.add(heapBig.peek());
                heapBig.poll();
            } // 保证左右两个堆的size最多差1
            if (!heapSmall.isEmpty() && heapBig.peek() > heapSmall.peek()) {
                heapSmall.add(heapBig.peek());
                heapBig.poll();
            } // 如果左边的最大值大于了右边的最小值，则移入右边
            if (heapSmall.size() > heapBig.size()) {
                heapBig.add(heapSmall.peek());
                heapSmall.poll();
            } // 如果右边的size大于左边，则移入左边，因为左边第一个为中位数
        }

分享一个插入的思路：

前提：设置一个大顶堆一个小顶堆，大顶堆中的顶部保存了中位数，大顶堆中其余元素都是排序后的中位数左边的元素；小顶堆中的元素都是大于中位数的元素；

在插入的时候要满足以下三个条件：

1. 大小顶堆size之差<=1;

2. 大顶堆的size>=小顶堆的size；

3. 大顶堆中的元素都小于小顶堆中的元素；

这样，大顶堆的第一个元素或者大顶堆第一个元素和小顶堆第一个元素的avg就是中位数啦。