Java中多路归并排序迭代器通过最小堆合并多个已排序Iterator，实现懒加载与内存友好；核心是IterEntry封装值与迭代器，用PriorityQueue维护各路首元素，next()时弹出堆顶并补充后续元素。
Java 中用 Iterator 实现多路归并排序迭代，核心是把多个**已排序的迭代器**合并成一个全局有序的迭代器。这不是一次性加载全部数据，而是按需拉取、懒加载，适合处理大文件、流式数据或内存受限场景。
准备：多个有序的 Iterator
确保你有多个实现了 Iterator<T> 的对象，且每个内部元素都已升序（或统一顺序）排列。例如：
- 多个已排序的数组转成的
Iterator - 多个已排序的文件行读取器（如
BufferedReader行迭代器） - 数据库分片查询返回的有序结果集迭代器
使用最小堆（PriorityQueue）管理各路首元素
Java 标准库没有直接的“多路归并 Iterator”，但可自己封装。关键步骤：
- 定义一个包装类（如
IterEntry<T>），保存当前值、所属迭代器引用，便于取值后继续推进 - 用
PriorityQueue<IterEntry<T>>维护每路的当前最小元素（按自然顺序或自定义Comparator） - 初始化时，对每个非空迭代器取一个元素，加入堆中
-
next()时弹出堆顶，将该元素所属迭代器的下一个元素（如果存在）推入堆中
示例关键逻辑（泛型简化版）：
立即学习“Java免费学习笔记（深入）”；
class MergedIterator<T> implements Iterator<T> {
private final PriorityQueue<IterEntry<T>> heap;
private final Comparator<? super T> cmp;
static class IterEntry<T> {
final T value;
final Iterator<T> iter;
IterEntry(T v, Iterator<T> it) { value = v; iter = it; }
}
public MergedIterator(List<Iterator<T>> iters, Comparator<? super T> cmp) {
this.cmp = cmp;
this.heap = new PriorityQueue<>((a, b) -> cmp.compare(a.value, b.value));
for (Iterator<T> it : iters) {
if (it.hasNext()) heap.offer(new IterEntry<>(it.next(), it));
}
}
public boolean hasNext() { return !heap.isEmpty(); }
public T next() {
IterEntry<T> top = heap.poll();
if (top.iter.hasNext()) {
heap.offer(new IterEntry<>(top.iter.next(), top.iter));
}
return top.value;
}
}
注意事项与优化点
-
空迭代器安全：初始化前过滤掉 null 或无元素的迭代器，避免
hasNext()异常 -
泛型类型一致性：所有输入迭代器应产出相同可比较类型，否则运行时可能
ClassCastException -
惰性求值保障：只在
next()时触发下一次拉取，不提前消费后续元素 -
资源释放（进阶）：若迭代器背后关联文件/连接，建议提供
close()方法或使用AutoCloseable封装
替代方案：用第三方库简化
不想手写？常用库已封装好：
-
Guava：
Iterators.mergeSorted(iterators, comparator)—— 返回懒求值的合并迭代器 -
Apache Commons Collections：
CollatingIterator（注意其线程不安全，且要求输入已排序） -
Vavr（原 Javaslang） 提供函数式风格的
Iterator.merge()
例如 Guava 一行搞定：
Iterator<Integer> merged = Iterators.mergeSorted(
Arrays.asList(it1, it2, it3),
Integer::compareTo
);
