排序算法之：利用“最小堆”和“最大堆”动态维护数据流的中位数——双堆策略详解 问题描述 假设我们有一个持续不断的数据流（例如实时的传感器读数、用户点击记录等）。我们需要在任意时刻，都能快速得到到目前为止所有已接收数据的中位数。如果数据个数为奇数，中位数是排序后的中间数；如果数据个数为偶数，中位数是中间两个数的平均值。 要求： 设计一个高效的数据结构，支持以下两个操作： addNum(int num) ：向数据结构中添加一个整数。 findMedian() ：返回当前所有数字的中位数。 时间复杂度要求： addNum 操作最好为 O(log n)， findMedian 操作最好为 O(1)，其中 n 是当前已添加的数字个数。 解题思路 直接的方法是在每次查询中位数时进行排序，但这样 findMedian 的时间复杂度为 O(n log n)，在数据流环境下效率极低。我们需要一种能动态维护有序结构的方法。 核心思想： 将整个数据集分成大致相等的两部分： 较小的一半 和 较大的一半 。 较小的一半用 最大堆（Max Heap） 存储，这样堆顶是这一半中的最大值。 较大的一半用 最小堆（Min Heap） 存储，这样堆顶是这一半中的最小值。 通过合理调整两个堆的大小和元素，使得最大堆的堆顶和最小堆的堆顶正好可以计算出中位数。 关键步骤： 新元素加入时，总是先放入最大堆（较小的一半）。 为了保证“较小的一半所有元素 ≤ 较大的一半所有元素”，需要将最大堆的堆顶（即较小一半的最大值）与最小堆的堆顶（即较大一半的最小值）进行比较和可能的交换。 保持两个堆的大小平衡：确保最大堆的大小始终等于或比最小堆多一个（当总数为奇数时，中位数就在最大堆的堆顶）。 这样，中位数就可以在 O(1) 时间内通过堆顶元素得到。 循序渐进讲解 第1步：数据结构设计 我们使用两个堆： maxHeap ：存储较小的一半数字，是一个最大堆（在多数编程语言中，通常通过存储负数或使用自定义比较器实现）。 minHeap ：存储较大的一半数字，是一个标准的最小堆。 初始化： 两个堆都为空。 第2步：插入操作的平衡规则 假设当前总共有 n 个数字， maxHeap 中有 m 个， minHeap 中有 k 个（ n = m + k ）。 平衡目标： 当 n 为偶数时，希望 m = k 。 当 n 为奇数时，希望 m = k + 1 （即中位数在 maxHeap 的堆顶）。 插入流程（ addNum ）： 将新元素 num 加入 maxHeap 。 因为 maxHeap 是较小的一半，新元素先放到这里，保证它有机会参与比较。 操作：将 num 插入 maxHeap ，时间复杂度 O(log n)。 平衡步骤： 从 maxHeap 中弹出堆顶（即当前较小一半的最大值），并将其插入 minHeap （较大的一半）。 这样做的目的是确保 maxHeap 中的任何元素都不大于 minHeap 中的任何元素（因为 maxHeap 的堆顶已经移到了 minHeap ）。 但这样可能导致 minHeap 的大小超过 maxHeap ，所以下一步进行大小调整。 大小调整： 检查两个堆的大小： 如果 minHeap 的大小 > maxHeap 的大小，说明较大的一半太多了，就将 minHeap 的堆顶（最小元素）移回 maxHeap 。 这保证了 maxHeap 的大小始终等于或比 minHeap 多一个。 为什么这样能保证顺序？ 因为每次操作都通过堆顶元素的交换，保证了 maxHeap 的所有元素 ≤ minHeap 的所有元素。同时，大小平衡规则保证了中位数总是可以从堆顶直接或间接得到。 第3步：获取中位数（ findMedian ） 如果 maxHeap 的大小 > minHeap 的大小，说明总数为奇数，中位数就是 maxHeap 的堆顶。 否则（大小相等），总数为偶数，中位数是 (maxHeap 堆顶 + minHeap 堆顶) / 2.0 。 第4步：举例说明 假设数据流依次为： [5, 3, 8, 2, 1] 。 步骤分解： 插入 5： maxHeap 加入 5 → maxHeap: [5] , minHeap: [] 。 平衡：弹出 maxHeap 堆顶 5 加入 minHeap → maxHeap: [] , minHeap: [5] 。 大小调整： minHeap 大小 > maxHeap 大小（1 > 0），将 minHeap 堆顶 5 移回 maxHeap → maxHeap: [5] , minHeap: [] 。 当前状态： maxHeap: [5] , minHeap: [] 。 插入 3： 加入 maxHeap → maxHeap: [5, 3] （最大堆，堆顶为 5）。 弹出 maxHeap 堆顶 5 加入 minHeap → maxHeap: [3] , minHeap: [5] 。 大小调整： minHeap 大小（1）不大于 maxHeap 大小（1），无需调整。 当前状态： maxHeap: [3] , minHeap: [5] 。 插入 8： 加入 maxHeap → maxHeap: [8, 3] （堆顶 8）。 弹出堆顶 8 加入 minHeap → maxHeap: [3] , minHeap: [5, 8] （最小堆，堆顶 5）。 大小调整： minHeap 大小（2）> maxHeap 大小（1），将 minHeap 堆顶 5 移回 maxHeap → maxHeap: [5, 3] , minHeap: [8] 。 当前状态： maxHeap: [5, 3] , minHeap: [8] 。 插入 2： 加入 maxHeap → maxHeap: [5, 3, 2] （堆顶 5）。 弹出堆顶 5 加入 minHeap → maxHeap: [3, 2] , minHeap: [5, 8] 。 大小调整： minHeap 大小（2）等于 maxHeap 大小（2），无需调整。 当前状态： maxHeap: [3, 2] , minHeap: [5, 8] 。 插入 1： 加入 maxHeap → maxHeap: [3, 2, 1] （堆顶 3）。 弹出堆顶 3 加入 minHeap → maxHeap: [2, 1] , minHeap: [3, 5, 8] 。 大小调整： minHeap 大小（3）> maxHeap 大小（2），将 minHeap 堆顶 3 移回 maxHeap → maxHeap: [3, 2, 1] , minHeap: [5, 8] 。 当前状态： maxHeap: [3, 2, 1] , minHeap: [5, 8] 。 此时求中位数： 总个数 5，奇数，中位数 = maxHeap 堆顶 = 3。 验证： 排序后的数组为 [1, 2, 3, 5, 8] ，中位数确实是 3。 如果再加一个数字 4： 加入后，总个数 6，偶数，中位数 = (maxHeap 堆顶 + minHeap 堆顶) / 2 。 执行插入 4 的步骤后，可以得到 maxHeap: [3, 2, 1] , minHeap: [4, 5, 8] 。 中位数 = (3 + 4) / 2 = 3.5 。 复杂度分析 时间复杂度： addNum ：每次最多进行两次堆插入和两次堆删除（弹出堆顶），每次堆操作 O(log n)，所以整体 O(log n)。 findMedian ：只访问堆顶，O(1)。 空间复杂度： O(n)，用于存储两个堆中的所有元素。 这种方法的优势在于它高效地利用了堆的性质，将排序和维护中位数的成本分摊到每次 O(log n) 的插入操作中，非常适合数据流场景。 关键点总结 双堆划分 ：用最大堆存较小一半，最小堆存较大一半。 插入时保证有序 ：通过交换堆顶，确保 maxHeap 堆顶 ≤ minHeap 堆顶。 大小平衡 ：通过移动堆顶元素，保持 maxHeap 的大小始终等于或比 minHeap 多一个。 中位数获取 ：根据堆大小奇偶性，直接取堆顶或平均值。 这种“双堆求中位数”的方法在算法竞赛和实际工程中都非常经典，是处理动态数据集中位数问题的标准高效解法。