多路归并（Multiway Merge / K-way Merge）— 5W1H故事与需求定义
051多路合并
Who（谁）
- 实现者：数据库工程师、大数据平台开发者、操作系统文件系统设计者
- 使用者：需要合并多个有序序列的系统，例如外部排序（磁盘 I/O 密集型排序）、数据库 merge join、日志合并、LSM 树（Log-Structured Merge Tree）的 compaction 过程
- 原著者：Donald E. Knuth，来自 TAOCP 第3卷 第5.4节（外部排序）
What（什么）
多路归并（K-way Merge）将 k 个已排好序的序列合并为一个有序序列。
核心数据结构是最小堆（Min-Heap）：
- 堆中每个节点记录三元组：
(当前值, 来自第几路, 该路下一个索引) - 每次从堆顶取出全局最小值，输出后将该路的下一个元素压入堆
- 时间复杂度：O(n log k)，其中 n 为元素总数，k 为路数
- 空间复杂度：O(k)（堆的大小始终为 k）
这与 Knuth TAOCP 5.4 节描述的"胜者树（Winner Tree）"在功能上等价，最小堆实现更为简洁直观。
When（何时）
- 外部排序：当数据量超过内存，需要将分块排序后的有序段合并时
- 数据库 Merge Join：合并来自不同有序数据集的记录
- LSM 树 Compaction：将多个有序 SSTable 合并为一个更大的 SSTable
- 流式数据合并：实时合并来自多个有序流的数据
Where（何处）
- 文件路径：
taocp_volume3/multiway_merge.c - 对应教材：TAOCP 第3卷 第5.4节，胜者树与多路归并
- 相关文件：归并排序（merge_sort.c）、替换选择（replacement_selection.c）、胜者树（winner_tree.c）
Why（为何）
- 外部排序核心：多路归并是磁盘排序中归并阶段的核心操作，直接影响 I/O 次数
- 工业级应用：LevelDB/RocksDB 的 compaction、Hadoop MapReduce 的 merge phase 均使用此算法
- O(n log k) 最优：相比朴素的逐一比较（O(nk)），堆优化使路数 k 增大时仍保持高效
- 教学价值：展示堆数据结构在"流式最小值提取"场景中的经典应用
- 可扩展性：算法天然支持 k 路并发读取，适合磁盘并行 I/O
How（如何）
算法步骤：
- 初始化堆：将每路第一个元素（如果存在）封装为
HeapNode(value, stream_id, next_idx)压入最小堆 - 循环提取：
while 堆非空: node = heap_pop() // 取出全局最小值 output[out_idx++] = node.value if node.next < sizes[node.stream]: // 该路还有元素 heap_push(HeapNode(arrays[node.stream][node.next], node.stream, node.next + 1)) - 终止：堆为空时所有序列已处理完毕
最小堆实现：
heap_sift_up：新元素压入后向上调整（O(log k)）heap_sift_down：弹出堆顶后将末尾元素移至堆顶，向下调整（O(log k)）
正确性保证：堆不变式确保每次弹出的都是当前所有路"队头"中的最小值。
需求定义
| 需求 ID | 描述 |
|---|---|
| REQ-01 | 实现kway_merge(arrays, sizes, k, output, total_size)合并 k 路有序数组 |
| REQ-02 | 使用最小堆作为优先级队列，保证 O(n log k) 时间复杂度 |
| REQ-03 | 支持路中含重复元素的情况，输出结果应保持有序（允许相等） |
| REQ-04 | k=1 的退化情形：直接输出单路内容 |
| REQ-05 | k=0 或 total_size=0 时返回 0，不崩溃 |
| REQ-06 | 堆使用动态内存分配，merge 完成后释放（无内存泄漏） |
| REQ-07 | 仅依赖<stdio.h>、<string.h>、<stdlib.h>，无外部库 |
验收标准
| 标准 ID | 验收条件 |
|---|---|
| AC-01 | 2路归并 [1,3,5] 和 [2,4,6]，输出恰好为 [1,2,3,4,5,6] |
| AC-02 | 3路归并 [1,4,7]、[2,5,8]、[3,6,9]，输出恰好为 [1,2,3,4,5,6,7,8,9] |
| AC-03 | 4路归并每路4个元素（共16个），输出有序且包含所有16个不重复元素 |
| AC-04 | 含重复元素的3路归并（共12个元素），输出有序 |
| AC-05 | k=1 单路退化：输出与输入一致；k=0 调用返回0不崩溃 |
| AC-06 | gcc -std=c99 -Wall编译无警告无错误 |
| AC-07 | 所有测试通过（tests_failed == 0），程序返回 0 |