01

60 秒回答模板

如果有 N 个数组且每个数组内部有序，可以把每个数组的第一个元素连同数组编号和下标放入小顶堆。每次弹出堆顶就是当前全局最小值，把它加入结果，然后把该元素所在数组的下一个元素放回堆。直到堆空，结果数组就是整体有序。时间复杂度是 O(M log N)，M 是总元素数，空间复杂度 O(N) 加结果空间。也可以两两归并，但在 N 较大时堆方法更直接。

考点 小顶堆维护最小候选
难度 真实面经题
回答目标 讲清方法、取舍和追问
02

深入解析

01

堆中存候选

每个数组只把当前未合并的最小元素放入堆，堆顶始终代表所有数组中的当前最小值。

02

弹出后推进

弹出某个数组的元素后，只需要把该数组下一个元素入堆，其他数组候选不变。

03

复杂度清晰

每个元素入堆和出堆一次，堆大小最多 N，因此总时间 O(M log N)，额外空间 O(N)。

04

适配流式输入

这个方法不要求把所有数组元素提前放入堆，只需要维护每个数组的当前游标，因此适合大文件、多路归并和外部排序场景，内存上界更容易控制。

05

处理边界条件

实现时要跳过空数组，比较函数要能处理重复值，结果数组容量可以按总长度预分配。面试手写时把数组编号和元素下标一起入堆，能避免弹出后找不到下一个元素。

06

对比替代方案

如果 N 很小，两两归并足够简单；如果 N 很大或输入来自多个文件流，小顶堆能稳定控制内存。回答时给出这个取舍，比只写一种代码更符合真实工程场景，也能顺带说明为什么堆里只保留每路当前候选，而不是保存所有元素。

javascript

小顶堆多路归并

function mergeSortedArrays(arrays) {
  const heap = new MinHeap((a, b) => a.value - b.value);
  const result = [];

  arrays.forEach((arr, arrayIndex) => {
    if (arr.length > 0) heap.push({ value: arr[0], arrayIndex, elementIndex: 0 });
  });

  while (heap.size() > 0) {
    const item = heap.pop();
    result.push(item.value);
    const nextIndex = item.elementIndex + 1;
    const source = arrays[item.arrayIndex];
    if (nextIndex < source.length) {
      heap.push({ value: source[nextIndex], arrayIndex: item.arrayIndex, elementIndex: nextIndex });
    }
  }

  return result;
}
  • 堆节点必须保存 `arrayIndex` 和 `elementIndex`，否则弹出后无法推进原数组。
  • 面试手写时可把 `MinHeap` 展开实现；讲思路时重点是堆大小始终不超过 N。
03

易错点

  • 不要把所有元素一次放进堆，那会把空间放大到 O(M)。
  • 不要忘记堆元素记录来自哪个数组和哪个下标。
  • 不要把复杂度写成 O(M log M)，优化点就在堆大小只有 N。
04

面试官追问

如果要降序输出怎么办？

可以用大顶堆，或从每个升序数组尾部开始推进，逻辑与小顶堆类似。

两两归并和堆合并怎么选？

两两归并实现简单，平衡归并也是 O(M log N)；堆合并更适合数组数量多、流式输入的情况。

如果数组特别大不能一次放内存？

可以只维护每个数组的当前游标和堆，数组从文件或迭代器流式读取，仍保持 O(N) 额外内存。