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

import java.util.*;

/**
 * NC131 数据流中的中位数
 * @author d3y1
 */
public class Solution {
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2) -> (o2-o1));

    /**
     * 堆排序: 最大堆+最小堆
     * 
     * 最大堆(较小一半) | 最小堆(较大一半)
     * 
     * 关键: 比较两次
     * 1. 与最大堆堆顶(较小一半的最大值)比较
     * 2. 与最小堆堆顶(较大一半的最小值)比较
     * 
     * @param num
     */
    public void Insert(Integer num) {
        // Insert1(num);
        // Insert11(num);
        // Insert2(num);
        Insert3(num);
    }

    private void Insert1(Integer num) {
        if(maxHeap.isEmpty() || maxHeap.size()>minHeap.size()){
            maxHeap.offer(num);
            if(maxHeap.size() > minHeap.size()+1){
                minHeap.offer(maxHeap.poll());
            }
        }else{
            minHeap.offer(num);
            if(minHeap.size() > maxHeap.size()){
                maxHeap.offer(minHeap.poll());
            }
        }
    }

    private void Insert11(Integer num) {
        if(maxHeap.size() > minHeap.size()){
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }else{
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }

    private void Insert2(Integer num) {
        if(maxHeap.isEmpty() || num<maxHeap.peek()){
            maxHeap.offer(num);
            if(maxHeap.size() > minHeap.size()+1){
                minHeap.offer(maxHeap.poll());
            }
        }else{
            minHeap.offer(num);
            if(minHeap.size() > maxHeap.size()){
                maxHeap.offer(minHeap.poll());
            }
        }
    }

    private void Insert3(Integer num) {
        if(maxHeap.size() == minHeap.size()){
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }else{
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }
    }

    /**
     * 获取中位数
     * @return
     */
    public Double GetMedian() {
        double result;
        // 奇数
        if(maxHeap.size() != minHeap.size()){
            result = maxHeap.peek();
            return result;
        }
        // 偶数
        else{
            result = (maxHeap.peek()+minHeap.peek())/2.0;
        }

        return result;
    }
}