排序算法之：多路归并排序（K-Way Merge Sort）的进阶应用：海量数据流的中位数查找

题目描述
假设有多个持续输入的数据流（每个流中的数据已排序），要求实时维护并快速返回当前所有数据流的中位数。例如，有 K 个传感器持续生成有序温度数据，需动态计算全局中位数。

解题思路

1. 问题分析

   • 数据量可能极大，无法全载入内存。
   • 中位数需动态更新：新数据到来时需快速调整。
   • 输入源为多个有序流，需高效合并与检索。

2. 核心策略

   • 用两个堆（最大堆+最小堆）维护中位数两侧数据，实现 O(log N) 插入。
   • 利用多路归并的思想，按需从 K 个流中逐批读取数据，避免一次性加载。

步骤详解

1. 数据结构设计

• 最大堆（左堆）：存储较小一半数据，堆顶为当前中位数候选。
• 最小堆（右堆）：存储较大一半数据，保证左堆大小 ≥ 右堆（中位数在左堆顶）。
• 平衡条件：
  • 若总数为奇数：左堆大小 = 右堆大小 + 1
  • 若总数为偶数：左堆大小 = 右堆大小

2. 动态插入数据

假设新数据来自多路归并的当前最小值（通过最小堆合并 K 个流）：

1. 比较新数据 x 与左堆顶：
   • 若 x ≤ left_max，插入左堆；否则插入右堆。
2. 调整平衡：
   • 若左堆大小 > 右堆大小 + 1：将左堆顶移入右堆。
   • 若右堆大小 > 左堆大小：将右堆顶移入左堆。

3. 多路归并的按需读取

• 维护一个大小为 K 的最小堆，存储每个流的当前首元素（值, 流索引, 流内位置）。
• 每次从堆顶取出最小值，插入中位数结构后，从对应流中读取下一个元素（若存在）加入堆。

4. 中位数计算

• 总数据量 N 为奇数：中位数 = 左堆顶
• N 为偶数：中位数 = (左堆顶 + 右堆顶) / 2

示例演示

假设有 3 个数据流：

流1: [10, 20, 30]  
流2: [15, 25]  
流3: [5, 35]  

初始化：

• 多路归并堆初始化为 [5(流3), 10(流1), 15(流2)]
• 中位数结构左右堆为空

步骤：

1. 取出最小值 5，插入左堆 → 左堆: [5], 右堆: []
2. 取出 10，因 10 > 5（左堆顶），插入右堆 → 左堆: [5], 右堆: [10]
3. 取出 15，插入右堆 → 左堆: [5], 右堆: [10,15]
   • 调整：右堆大小(2) > 左堆大小(1)，将右堆顶 10 移入左堆 → 左堆: [10,5], 右堆: [15]
4. 当前中位数（N=3）为左堆顶 10

复杂度分析

• 时间复杂度：
  • 每次插入堆操作 O(log N)，N 为当前总数据量。
  • 多路归并每次取最小值 O(log K)。
• 空间复杂度：O(K + N)，但通过流式读取可控制内存使用。

优化与边界处理

• 内存限制：若数据量极大，可定期丢弃极端值（如仅保留中位数附近数据）。
• 流结束处理：某流耗尽时，继续从剩余流中合并。
• 重复数据：堆结构天然支持重复值，不影响中位数计算。

此方法将多路归并的按需特性与堆的动态平衡结合，适用于海量数据流的实时中位数计算。