051多路归并

多路归并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.cWhy为何外部排序核心多路归并是磁盘排序中归并阶段的核心操作直接影响 I/O 次数工业级应用LevelDB/RocksDB 的 compaction、Hadoop MapReduce 的 merge phase 均使用此算法O(n log k) 最优相比朴素的逐一比较O(nk)堆优化使路数 k 增大时仍保持高效教学价值展示堆数据结构在流式最小值提取场景中的经典应用可扩展性算法天然支持 k 路并发读取适合磁盘并行 I/OHow如何算法步骤初始化堆将每路第一个元素如果存在封装为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-04k1 的退化情形直接输出单路内容REQ-05k0 或 total_size0 时返回 0不崩溃REQ-06堆使用动态内存分配merge 完成后释放无内存泄漏REQ-07仅依赖stdio.h、string.h、stdlib.h无外部库验收标准标准 ID验收条件AC-012路归并 [1,3,5] 和 [2,4,6]输出恰好为 [1,2,3,4,5,6]AC-023路归并 [1,4,7]、[2,5,8]、[3,6,9]输出恰好为 [1,2,3,4,5,6,7,8,9]AC-034路归并每路4个元素共16个输出有序且包含所有16个不重复元素AC-04含重复元素的3路归并共12个元素输出有序AC-05k1 单路退化输出与输入一致k0 调用返回0不崩溃AC-06gcc -stdc99 -Wall编译无警告无错误AC-07所有测试通过tests_failed 0程序返回 0