1. 概述
本文将介绍如何利用堆（Heap）结构高效地合并多个已排序的数组。这是一个在实际开发中经常遇到的经典问题，比如多路归并、外部排序等场景。使用最小堆（min-heap）可以将时间复杂度控制在一个非常理想的范围内，避免暴力合并带来的性能损耗。
2. 算法原理
我们的问题目标是：合并 k 个已排序的数组，输出一个整体有序的结果数组。为了高效解决这个问题，采用 最小堆（min-heap） 是一种经典且高效的策略。
✅ 什么是 min-heap？
min-heap 是一种特殊的二叉树结构，满足以下性质：
- 根节点的值是整个树中最小的；
- 每个节点的值都小于等于其左右子节点的值。
通常，min-heap 使用数组实现，通过下标关系快速定位父子节点：
对于数组 A[] 中索引为 i 的元素：
- 父节点索引：
(i - 1) / 2 - 左子节点索引：
2 * i + 1 - 右子节点索引：
2 * i + 2
下面是 min-heap 的图示及其对应的数组表示：
🔧 合并算法步骤
要合并多个有序数组，我们可以按如下流程操作：
- ✅ 创建结果数组，总长度为所有输入数组长度之和。
- ✅ 取每个数组的首个元素，构建一个大小为
k（数组个数）的初始堆。 - ✅ 将该数组构造成 min-heap。
- ✅ 重复以下步骤直到结果数组填满：
- 提取堆顶（最小值），放入结果数组；
- 从该元素来源的原数组中取出下一个元素，替换堆顶；
- 重新调整堆结构（heapify），维持 min-heap 性质。
⚠️ 时间复杂度分析
- 总共需要处理
k个数组中的所有元素，设总元素个数为N。 - 每次 heapify 操作的时间复杂度是
O(log k)，因为堆的高度是log k。 - 因此整体时间复杂度为：**
O(N log k)**
💡 对比：如果直接合并再排序，复杂度会退化到
O(N log N)，当k << N时，O(N log k)明显更优。
🧪 示例输入与输出
输入数组：
{ { 0, 6 }, { 1, 5, 10, 100 }, { 2, 4, 200, 650 } }
期望输出：
{ 0, 1, 2, 4, 5, 6, 10, 100, 200, 650 }
这个例子能直观展示算法如何从小到大逐个“挑选”最小元素。
3. Java 实现
接下来我们用 Java 实现上述算法。核心思路是使用两个类：
HeapNode：封装堆中每个节点的信息；MinHeap：实现堆的操作和合并逻辑。
3.1. 堆节点定义（HeapNode）
我们需要知道每个堆节点的值来自哪个数组，以及下一个待取元素的位置。
public class HeapNode {
int element; // 当前元素值
int arrayIndex; // 来自第几个数组（索引）
int nextElementIndex = 1; // 下一个要取的元素在原数组中的位置
public HeapNode(int element, int arrayIndex) {
this.element = element;
this.arrayIndex = arrayIndex;
}
}
✅ 说明：
arrayIndex用于定位该元素来自哪个输入数组；nextElementIndex初始为 1，表示下次从原数组的 index=1 处取数；- 我们省略了 getter/setter 以保持代码简洁，生产环境可根据需要补充。
3.2. MinHeap 类与合并逻辑
public class MinHeap {
HeapNode[] heapNodes;
public MinHeap(HeapNode heapNodes[]) {
this.heapNodes = heapNodes;
heapifyFromLastLeafsParent();
}
int getParentNodeIndex(int index) {
return (index - 1) / 2;
}
int getLeftNodeIndex(int index) {
return (2 * index + 1);
}
int getRightNodeIndex(int index) {
return (2 * index + 2);
}
HeapNode getRootNode() {
return heapNodes[0];
}
// 调整以 index 为根的子树，使其满足 min-heap 性质
void heapify(int index) {
int leftNodeIndex = getLeftNodeIndex(index);
int rightNodeIndex = getRightNodeIndex(index);
int smallestElementIndex = index;
if (leftNodeIndex < heapNodes.length
&& heapNodes[leftNodeIndex].element < heapNodes[index].element) {
smallestElementIndex = leftNodeIndex;
}
if (rightNodeIndex < heapNodes.length
&& heapNodes[rightNodeIndex].element < heapNodes[smallestElementIndex].element) {
smallestElementIndex = rightNodeIndex;
}
if (smallestElementIndex != index) {
swap(index, smallestElementIndex);
heapify(smallestElementIndex); // 递归调整
}
}
// 从最后一个叶子节点的父节点开始，自底向上构建堆
void heapifyFromLastLeafsParent() {
int lastLeafsParentIndex = getParentNodeIndex(heapNodes.length - 1);
while (lastLeafsParentIndex >= 0) {
heapify(lastLeafsParentIndex);
lastLeafsParentIndex--;
}
}
// 交换两个节点
private void swap(int i, int j) {
HeapNode temp = heapNodes[i];
heapNodes[i] = heapNodes[j];
heapNodes[j] = temp;
}
// 主方法：合并 k 个有序数组
public static int[] merge(int[][] arrays) {
int k = arrays.length;
if (k == 0) return new int[0];
// Step 1: 初始化 heapNodes，取每个数组的第一个元素
HeapNode[] heapNodes = new HeapNode[k];
int totalSize = 0;
for (int i = 0; i < k; i++) {
if (arrays[i].length == 0) continue; // 跳过空数组
heapNodes[i] = new HeapNode(arrays[i][0], i);
totalSize += arrays[i].length;
}
MinHeap minHeap = new MinHeap(heapNodes);
int[] result = new int[totalSize];
// Step 2: 循环提取最小值并补充新元素
for (int i = 0; i < totalSize; i++) {
HeapNode root = minHeap.getRootNode();
result[i] = root.element;
// 判断是否还有下一个元素可取
if (root.nextElementIndex < arrays[root.arrayIndex].length) {
root.element = arrays[root.arrayIndex][root.nextElementIndex++];
} else {
// 没有更多元素了，设为最大值占位（相当于移除）
root.element = Integer.MAX_VALUE;
}
// 重新调整堆
minHeap.heapify(0);
}
return result;
}
}
⚠️ 关键点说明：
- 使用
Integer.MAX_VALUE作为“已耗尽数组”的标记，确保它不会再被选为最小值；heapify(0)每次只调整根节点，因为只有根被修改了；heapifyFromLastLeafsParent()保证初始堆结构正确。
4. 测试验证
我们用前面提到的例子进行测试，确保逻辑正确。
import org.junit.jupiter.api.Test;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.*;
public class MinHeapTest {
@Test
public void givenSortedArrays_whenMerge_thenSuccess() {
int[][] inputArray = {
{ 0, 6 },
{ 1, 5, 10, 100 },
{ 2, 4, 200, 650 }
};
int[] expectedArray = { 0, 1, 2, 4, 5, 6, 10, 100, 200, 650 };
int[] resultArray = MinHeap.merge(inputArray);
assertThat(resultArray.length, is(equalTo(10)));
assertThat(resultArray, is(equalTo(expectedArray)));
}
}
✅ 测试通过，结果符合预期。
💡 提示：实际项目中建议增加边界测试，如空数组、单数组、含重复元素等情况。
5. 总结
本文介绍了如何使用 min-heap 高效合并多个有序数组，核心思想是：
- 利用堆快速获取当前最小值；
- 动态维护 k 个候选元素（每数组一个）；
- 时间复杂度稳定在
O(N log k)，远优于暴力合并。
这种模式在实际开发中非常实用，比如：
- 多路归并排序；
- 分布式系统中合并多个有序数据流；
- 日志聚合、搜索引擎结果合并等。
🔗 示例代码已托管至 GitHub：https://github.com/example-java/algorithm-demo/tree/main/merge-sorted-arrays
掌握这个技巧，下次遇到类似问题就能简单粗暴地秒了。