1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,
            b)->(b - a)); //大顶堆存较小的一半
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b)->(a - b));

    public void Insert(Integer num) {
        if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
            maxHeap.add(num);
        } else {
            minHeap.add(num);
        }
        balance();
    }

    public Double GetMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (double)((maxHeap.peek() + minHeap.peek()) / 2.0);
        } else {
            return (double)(maxHeap.size() > minHeap.size() ? maxHeap.peek() :
                            minHeap.peek());
        }
    }

    private void balance() {
        if (Math.abs(maxHeap.size() - minHeap.size()) == 2) {
            if (maxHeap.size() > minHeap.size()) {
                minHeap.add(maxHeap.poll());
            } else {
                maxHeap.add(minHeap.poll());
            }
        }
    }