0295. 数据流的中位数

[giscus[bot]]

0295. 数据流的中位数 | 算法通关手册

295. 数据流的中位数 # 标签：设计、双指针、数据流、排序、堆（优先队列） 难度：困难 题目大意 # 要求：设计一个支持一下两种操作的数组结构： void addNum(int num)

https://algo.itcharge.cn/Solutions/0200-0299/find-median-from-data-stream/

[hein-hp]

题解的思路有点问题：应该是小根堆记录大于中位数的数吧，然后大根堆记录小于中位数的数，这样才能拿到大于中位数的最小的数，和小于中位数的最大的数

[hein-hp]

再者说，你如何能拿到小根堆的最大值，大根堆的最小值呢？

[hein-hp]

使用一个小根堆 $minHeap$ 记录大于中位数的数，使用一个大根堆 $maxHeap$ 小于等于中位数的数。

• 当添加元素数量为偶数： $minHeap$ 和 $maxHeap$ 中元素数量相同，则中位数为它们堆顶元素的平均值。
• 当添加元素数量为奇数：$maxHeap$ 中的数比 $minHeap$ 多一个，此时中位数为 $maxHeap$ 的队头。

为了满足上述条件，在进行 $addNum$ 操作时，应当分情况处理：

• $num>max(maxHeap)$：此时 $num$ 大于中位数，将该数添加到小根堆 $minHeap$ 中。新的中位数将大于原来的中位数，所以可能需要将 $minHeap$ 中的最小数（$minHeap$ 的堆顶元素）移动到 $maxHeap$ 中。
• $num\le max(maxHeap)$：此时 $num$ 小于中位数，将该数添加到大根堆 $maxHeap$ 中。新的中位数将小于等于原来的中位数，所以可能需要将 $maxHeap$ 中最大数（$maxHeap$ 的堆顶元素）移动到 $minHeap$ 中。