【剑指offer】数据流中的中位数

膜拜笔者的引入思路：
讨论哪种数据结构存储数据 -> 引出数组 -> 排序的链表 -> 二叉搜索树 -> 优化的AVL树 -> 最后到堆，真是让人深感佩服。

// 以前写代码着重代码的简洁，现在写代码在复杂度相同的情况下，先可读性，再简洁性。

import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {

    Queue<Integer> minHeap = new PriorityQueue<>();
    Queue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
    int count = 0;

    public void Insert(Integer num) {
        if ((++count & 1) == 1) { // 数据总数为奇数放最大堆
            if (!minHeap.isEmpty() && minHeap.peek() < num) {
                int t = minHeap.poll();
                minHeap.add(num);
                maxHeap.add(t);
            } else {
                maxHeap.add(num);
            }

        } else { // 数据总数为偶数放最小堆
            if (maxHeap.peek() > num) {
                int t = maxHeap.poll();
                maxHeap.add(num);
                minHeap.add(t);
            } else {
                minHeap.add(num);
            }
        }
    }

    public Double GetMedian() {
        if ((count & 1) == 1) {
            return (double) maxHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}