题解 | #数据流中的中位数#

数据分成两份 a 和 b，a的数都比b大， a使用小根堆表示，b使用大根堆表示。维持a和b的数据量保持a.size==b.size或者a.size + 1 = b.size的关系。 中位数：如果总数是偶数个，则a.size==b.size，取两个堆顶的平均值；奇数个，则a.size + 1 = b.size，取b的堆顶的值

import java.util.*;
public class Solution {

    PriorityQueue<Integer> bigHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    PriorityQueue<Integer> smallHeap = new PriorityQueue<>(Comparator.comparingInt(
                o -> o));

    public void Insert(Integer num) {
        if (bigHeap.isEmpty() || bigHeap.peek() > num) {
            bigHeap.add(num);
        } else {
            smallHeap.add(num);
        }
        if (smallHeap.size() > bigHeap.size()) {
            bigHeap.add(smallHeap.poll());
        } else if (smallHeap.size() + 1 < bigHeap.size()) {
            smallHeap.add(bigHeap.poll());
        }
    }

    public Double GetMedian() {
        return bigHeap.size() > smallHeap.size() ? bigHeap.peek() * 1.0 :
               (smallHeap.peek() + bigHeap.peek()) / 2.0;
    }


}