Julia：使用迭代器按有序合并多个已排序流的实现方法

要实现内存友好的多有序数组合并，核心思路是用**优先队列（堆）**跟踪每个迭代器的当前头部元素，每次取出最小的元素，再补充对应迭代器的下一个元素，直到所有迭代器耗尽。这种方式的内存占用仅和迭代器数量相关，完全适合超大数组的场景。

实现步骤（以Python为例） #

1. 初始化堆：把每个输入转换成迭代器，取出第一个元素（如果迭代器非空），将（当前值，迭代器）的元组推入堆，堆会自动按值排序。
2. 循环取最小元素：弹出堆顶的最小元素并返回，然后尝试从对应迭代器取下一个元素，若存在则重新推入堆。
3. 处理空迭代器：初始化和循环中都跳过已耗尽的迭代器，避免无效操作。

完整代码示例 #

import heapq

def merge_sorted_iterators(*iters):
    heap = []
    # 初始化堆，处理每个输入迭代器
    for it in iters:
        iterator = iter(it)
        try:
            first_val = next(iterator)
            heapq.heappush(heap, (first_val, iterator))
        except StopIteration:
            # 空迭代器直接跳过
            pass
    
    while heap:
        current_val, current_iter = heapq.heappop(heap)
        yield current_val
        # 尝试获取下一个元素
        try:
            next_val = next(current_iter)
            heapq.heappush(heap, (next_val, current_iter))
        except StopIteration:
            pass

# 测试示例
a = [1, 1, 4, 5, 8, 9]
b = [2, 6, 7]
# 可添加更多测试数组
c = [3, 3, 10]

# 遍历合并后的迭代器
for val in merge_sorted_iterators(a, b, c):
    print(val, end=' ')
# 输出结果：1 1 2 3 3 4 5 6 7 8 9 10

关键特性说明 #

• 内存友好：堆中始终只保留每个迭代器的当前头部元素，内存复杂度为O(k)（k是迭代器数量），和原数组大小无关，完美适配超内存数组。
• 支持任意数量迭代器：通过*iters可变参数接收任意多个输入，不管是2个还是N个都能处理。
• 兼容重复值：堆会自动按值排序，重复元素会被依次取出，不会破坏有序性。

内容的提问来源于stack exchange，提问作者BAR