数据结构与算法 / 系统课时

用多路归并处理有序数据源

用多路归并处理有序数据源

当输入不是一个数组,而是多个已经各自有序的序列时,重新拼接后整体排序会浪费已有顺序。多路归并只把每个数据源当前最小的候选放进小根堆,每次取出全局最小值,再从同一数据源补入下一个元素。

学习目标

  • 理解多路归并为什么只需保存每个数据源的一个候选
  • 使用小根堆合并多个有序序列
  • 将相同机制改造成第 K 小元素查询

从多个有序序列选出全局最小值

假设有 M 个升序序列。任意时刻,每个序列尚未处理部分的最小值一定在自己的当前位置,因此全局最小值只可能来自这 M 个候选,而不需要检查后面的元素。

把每个非空序列的第一个元素加入小根堆。弹出最小候选后,它所在序列的下一个元素才获得成为全局最小值的资格,于是把这个后继压入堆。堆中始终最多只有 M 个元素。

多路归并中各有序数据源与最小堆的候选更新流程

实现归并与第 K 小查询

堆元素除了数值,还要保存它来自哪个序列以及在该序列中的位置。这样弹出一个值后,才能准确找到同一路的后继。

python
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))

预期输出

text
[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 小问题。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用多路归并处理有序数据源

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通