295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

• -10^5 <= num <= 10^5
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 10^4 次调用 addNum 和 findMedian

一个小顶堆+一个大顶堆，过滤

注意：我们不能将元素只加入其中一个堆，这样可能破坏两个堆之间大顶堆堆顶 < 小顶堆的堆顶的关系；必须将加入的元素在两个堆之间都过一遍，使堆维持其特性。

class MedianFinder {
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    
    // 我们不能将元素只加入其中一个堆，这样可能破坏两个堆之间大顶堆堆顶 < 小顶堆的堆顶的关系；必须将加入的元素在两个堆之间都过一遍，使堆维持其特性
    // 要往一个堆中加元素，一定要经过另外一个堆的过滤，因为我们要加的元素未必属于这个堆。
    // A中的元素 > A堆顶的元素 > B堆顶的元素 > B中的元素
    public void addNum(int num) {
        // A和B元素个数不相等时，A的元素个数一定大于B（因为我们在它们元素个数相等时是往A中加的元素），所以我们要往B中加新元素，而这需要经过A的过滤。
        if (A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else { // 两个堆元素个数相等时，因为下面我们用的是A.peek()，所以我们要往A中加元素，而这必须经过B的过滤。
            // 比如(8>7)>(6>5)，我们加入4，应该把4加入B，把弹出来的6加入A。
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        // 注意要除以 2.0，不然返回的是 int 类型
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

• 时间复杂度 O(log N)：
  • 查找中位数 O(1)： 获取堆顶元素使用 O(1) 时间。
  • 添加数字 O(log N)： 堆的插入和弹出操作使用 O(log N) 时间。
• 空间复杂度 O(N)： 其中 N 为数据流中的元素数量，小顶堆 A 和大顶堆 B 最多同时保存 N 个元素。

为什么堆的插入和弹出操作是 O(log N) 时间复杂度？

堆的性质：

• 堆是一棵完全二叉树，所有节点都必须满足堆的性质：
  • 在小顶堆中，每个父节点的值都小于或等于其子节点的值。
  • 在大顶堆中，每个父节点的值都大于或等于其子节点的值。

插入操作：

• 插入操作需要将新元素放到堆的末尾，然后进行“上浮”操作，以确保堆的性质不被破坏。
• 上浮操作的时间复杂度为 O(log n)，因为最坏情况下需要从叶子节点移动到根节点，路径长度为堆的高度，而完全二叉树的高度为 O(log n)。

弹出操作：

• 弹出操作通常是弹出堆顶元素，然后用堆的末尾元素替代堆顶，并进行“下沉”操作，以确保堆的性质不被破坏。
• 下沉操作的时间复杂度为 O(log n)，因为最坏情况下需要从根节点移动到叶子节点，路径长度为堆的高度，而完全二叉树的高度为 O(log n)。