1. k 路归并如何用最小堆在每轮选全局最小维持 O(n log k)
问题
k 路归并如何用最小堆在每轮选全局最小，从而维持 O(n log k) 的时间复杂度？
考察点
- 最小堆维护 k 个候选
- 每轮取堆顶 O(log k)
- 总复杂度 O(n log k)
答案
k 路归并把 k 个已排序序列（归并段）合并成一个有序序列。用最小堆存放每个序列当前的最小元素（共 k 个），每轮：弹出堆顶（全局最小）写入输出，再从该序列取下一个元素入堆，重复直到全部取完。每轮取堆顶和插入都是 O(log k)，共 n 个元素，总复杂度 O(n log k)。相比两两归并 O(n log k)，k 路归并减少归并趟数。
解析
最小堆维护 k 个"当前最小"，从堆顶取全局最小，从来源序列取下一个补入，保证有序。每次操作 O(log k)，n 个元素总 O(n log k)。k 路归并是外部排序多路归并的核心，降低 I/O 趟数。
示例代码
import java.util.*;
// k 路归并：list 为 k 个已排序序列，数组元素为 [值, 序列号]
int[] kWayMerge(List<int[]> lists) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
int[] idx = new int[lists.size()];
for (int i = 0; i < lists.size(); i++) if (lists.get(i).length > 0)
pq.offer(new int[]{lists.get(i)[0], i});
List<Integer> res = new ArrayList<>();
while (!pq.isEmpty()) {
int[] cur = pq.poll();
res.add(cur[0]);
int i = cur[1];
if (++idx[i] < lists.get(i).length)
pq.offer(new int[]{lists.get(i)[idx[i]], i});
}
return res.stream().mapToInt(x->x).toArray();
}