数据结构与算法 / 系统课时
用多路归并处理有序数据源
用多路归并处理有序数据源
当输入不是一个数组,而是多个已经各自有序的序列时,重新拼接后整体排序会浪费已有顺序。多路归并只把每个数据源当前最小的候选放进小根堆,每次取出全局最小值,再从同一数据源补入下一个元素。
学习目标
- 理解多路归并为什么只需保存每个数据源的一个候选
- 使用小根堆合并多个有序序列
- 将相同机制改造成第 K 小元素查询
从多个有序序列选出全局最小值
假设有 M 个升序序列。任意时刻,每个序列尚未处理部分的最小值一定在自己的当前位置,因此全局最小值只可能来自这 M 个候选,而不需要检查后面的元素。
把每个非空序列的第一个元素加入小根堆。弹出最小候选后,它所在序列的下一个元素才获得成为全局最小值的资格,于是把这个后继压入堆。堆中始终最多只有 M 个元素。

实现归并与第 K 小查询
堆元素除了数值,还要保存它来自哪个序列以及在该序列中的位置。这样弹出一个值后,才能准确找到同一路的后继。
import heapq
def build_heap(sources):
heap = []
for source_index, values in enumerate(sources):
if values:
# 三元组同时记录值、来源和位置,便于找到同一路的后继。
heapq.heappush(heap, (values[0], source_index, 0))
return heap
def merge_sorted_sources(sources):
heap = build_heap(sources)
result = []
while heap:
value, source_index, item_index = heapq.heappop(heap)
result.append(value)
next_index = item_index + 1
if next_index < len(sources[source_index]):
next_value = sources[source_index][next_index]
heapq.heappush(heap, (next_value, source_index, next_index))
return result
def kth_smallest(sources, k):
if k <= 0:
raise ValueError("k must be positive")
heap = build_heap(sources)
count = 0
while heap:
value, source_index, item_index = heapq.heappop(heap)
count += 1
if count == k:
return value
next_index = item_index + 1
if next_index < len(sources[source_index]):
next_value = sources[source_index][next_index]
heapq.heappush(heap, (next_value, source_index, next_index))
raise ValueError("k exceeds the total number of elements")
if __name__ == "__main__":
sources = [[1, 4, 8], [2, 3, 10], [5, 6, 7]]
print(merge_sorted_sources(sources))
print(kth_smallest(sources, 7))预期输出
[1, 2, 3, 4, 5, 6, 7, 8, 10]
7为什么第 K 小不必完成全部归并
完整归并会不断弹出堆顶,输出顺序就是所有元素从小到大的顺序。因此第 K 次弹出的值天然就是全局第 K 小。只要求第 K 小时,到第 K 次弹出即可停止,后续元素完全不需要处理。
这也是识别题型的重要信号:如果题目给出多个有序数组、链表、行或数据流,并询问整体顺序、前 K 个值或第 K 小值,可以先考虑“每一路只提供一个当前候选”的多路归并,而不是把全部数据复制出来再排序。
复杂度与实现边界
设所有序列元素总数为 N,序列数量为 M。完整归并进行 N 次弹出,并至多进行 N 次压入,每次堆操作的规模不超过 M,因此时间复杂度为 O(N log M),堆额外空间为 O(M)。如果只查询第 K 小,则通常只处理前 K 个结果,时间复杂度为 O(K log M)。
空序列不应加入初始堆;K 超过元素总数时必须明确报错或按题意返回约定值。多个序列中存在相同数字不会破坏算法,因为来源索引与位置一起保留了候选身份。
多路归并真正利用的是局部有序带来的候选压缩:无论每个序列有多长,任意时刻每一路只需要暴露一个元素。堆负责在这些候选之间做全局选择,因此特别适合合并 K 个有序链表、多个升序数组以及有序矩阵中的第 K 小问题。