数据流中的中位数_JAVA_中等

• 维护一个低位堆，一个高位堆，保持高位堆不少于低位堆，且低位堆最多比高位堆少一
• 如果高位堆比低位堆大1，则取高位堆最小值，否则取低位堆最大值和高位堆最小值的平均数
• 而优先队列能维护一个大（小）根堆，保证在O(1)找出低位堆最大值和高位堆最小值

import java.util.*;
public class Solution {
    // 低位用大根堆
    PriorityQueue<Integer> low = new PriorityQueue(new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });

    // 高位用小根堆
    PriorityQueue<Integer> high = new PriorityQueue();
    public void Insert(Integer num) {
        // 低位比高位少时增加低位
        if(low.size() < high.size()) {
            // 如果该数该进大根堆则置换出大根堆的数
            if(num > high.peek()) {
                high.offer(num);
                num = high.poll();
            }
            low.offer(num);
        // 否则增加高位
        } else {
            // 如果该数该进小根堆则置换出小根堆的数
            if(!low.isEmpty() && num < low.peek()) {
                low.offer(num);
                num = low.poll();
            }
            high.offer(num);
        }
    }

    public Double GetMedian() {
        return high.size() > low.size() ? (double)high.peek() : (high.peek() + low.peek()) / 2.0;
    }
}