295. Median Finder

Find Median from Data Stream

Heaps的重点应用 不仅是实时查最小值或最大值

还能在数据流中实时盯著中位数

数据流的中位数定义

• 长度$n$是奇数：排序后 正中央那个数 比如$[1, 2, 3]$的中位数是$2$
• 长度$n$是偶数：排序后 中间那俩数平均 比如$[1, 2, 3, 4]$的中位数是$(2 + 3) / 2 = 2.5$

定义好了后 我们就要看 不停加入新的数字时

如何随时知道排序后的中位数是谁

排序的言下之意

一个排序好的序列 显然能拆成上下俩半身

下半身的『最大』肯定$\leq$上半身的『最小』

因此我们能准备一个min_heap 一个max_heap

min_heap维护上半身 max_heap维护下半身

然后要遵守下方的条件：

I. 双方尺寸要嘛一样 要么min_heap比max_heap多一个元素

若数据流目前有奇数个元素时 中位数会在min_heap这儿

也是此时min_heap比max_heap多一个元素

当然这是因为我习惯让中位数去上半身

选择放下半身其实也行 纯属个人偏好 有统一就好

II. max_heap最大值$\leq$min_heap最小值

没做到的话 就要不停双方交换 直到做到为止

新元素来时 先看Heaps尺寸

• 若两个堆尺寸一样 就把新元素丢到min_heap

• 若min_heap比max_heap多一个元素 新元素丢max_heap

现在我们已经执行完毕前述的条件I

接下来 我们要检查 是否得矫正双堆

也就是如果max_heap最大值$\gt$min_heap最小值

那么max_heap最大值升级去min_heap

同理min_heap最小值降级去max_heap

形成双方交易 交易到何时停止捏？

做到这句不等式即可结束矫正：

max_heap最大值$\leq$min_heap最小值

此刻条件II也满足啦～～👌👌

查找中位数 还是回到双堆尺寸

A. 若min_heap比max_heap多一个元素

中位数就是min_heap最小值

B. 若两个堆尺寸一样 中位数是

min_heap最小值和max_heap最大值的平均数

Python和C++预设不太一样⚠️

Python的heapq预设min heap

C++的priority_queue预设max heap

不是预设的那个半身 要记得negate数值

就是给数值加上负号 才能让

预设min heap的也做得了max heap 反之亦然

C++

#include <queue>
using namespace std;

class MedianFinder // LeetCode Q.295.
{
private:
    // When nums count is odd, median goes to min heap.
    // Min heap needs to negate value to fit default C++ max heap.
    priority_queue<int> minHeap, maxHeap;

public:
    MedianFinder() {}

    void addNum(int num) {
        if (maxHeap.size() == minHeap.size())
            minHeap.push(-num); // Min heap negates.

        else
            maxHeap.push(num);

        while (!maxHeap.empty() && !minHeap.empty()) {
            if (maxHeap.top() <= -minHeap.top()) // Min heap negates.
                break; // No need to adjust.

            // Max heap top > -min heap top: mismatch so must switch.
            minHeap.push(-maxHeap.top()); // Min heap negates.
            maxHeap.push(-minHeap.top()); // Min heap negates.

            minHeap.pop();
            maxHeap.pop();
        }
    }

    double findMedian() {
        if (minHeap.size() > maxHeap.size()) // Min heap negates.
            return -minHeap.top();
        return (maxHeap.top() - minHeap.top()) * 0.5; // Min heap negates.
    }
};

Python

import heapq


class MedianFinder:  # LeetCode Q.295.
    def __init__(self):
        # When nums count is odd, median goes to min heap.
        # Max heap needs to negate value to fit default Python min heap.
        self.min_heap: list[int] = []
        self.max_heap: list[int] = []

    def add_num(self, num: int) -> None:
        if len(self.max_heap) == len(self.min_heap):
            heapq.heappush(self.min_heap, num)

        else:
            heapq.heappush(self.max_heap, -num)  # Max heap negates.

        while self.max_heap and self.min_heap:
            if -self.max_heap[0] <= self.min_heap[0]: break  # No need to adjust.

            # -Max heap top > min heap top: mismatch so must switch.
            former_max_heap_top = -heapq.heappop(self.max_heap)  # Max heap negates.
            heapq.heappush(self.min_heap, former_max_heap_top)

            former_min_heap_top = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -former_min_heap_top)  # Max heap negates.

    def find_median(self) -> float:
        if len(self.min_heap) > len(self.max_heap):
            return self.min_heap[0]

        return (self.min_heap[0] - self.max_heap[0]) / 2  # Max heap negates.

LeetCode题目页Python区的 addNum和findMedian

就是我的add_num和find_median

我习惯在C++才写🐫camel cases

Python我惯用🐍snake cases

加入新元素 需要$O(logn)$时间维护双堆 查找中位数仅需要$O(1)$时间

空间自然一直都是$O(n)$了

我强烈推荐Tim Roughgarden教授的算法教程

除了Median Maintenance 还有不少非常有趣的Heaps应用 和最基础的堆原理解析