堆排序（Heap Sort）是一种基于比较的排序算法，它巧妙地将数组视为一棵完全二叉树，通过”堆化”操作在原地完成排序。与快速排序相比，堆排序在最坏情况下仍能保持 O(n log n) 的时间复杂度，且不需要额外的递归栈空间。本文将从完全二叉树的数组表示出发，深入讲解最大堆的构建、下沉（sift down）与上浮（sift up）操作，并给出完整的 Java 实现，最后扩展到优先队列与 Top K 问题的实战应用。
一、完全二叉树的数组表示
在堆排序中，我们不需要定义真正的树节点结构。一个普通数组即可隐式表示一棵完全二叉树：
- 对于索引
i处的节点： - 父节点索引：
parent(i) = (i - 1) / 2 - 左子节点索引：
left(i) = 2 * i + 1 - 右子节点索引：
right(i) = 2 * i + 2
这种表示法的优势在于无需额外的指针开销，所有操作都在数组上通过索引计算完成，空间利用率极高。
/**
* 堆的工具类：提供索引计算与常用操作
*/
public class HeapUtils {
/**
* 获取父节点索引
*/
public static int parent(int i) {
return (i - 1) / 2;
}
/**
* 获取左子节点索引
*/
public static int left(int i) {
return 2 * i + 1;
}
/**
* 获取右子节点索引
*/
public static int right(int i) {
return 2 * i + 2;
}
/**
* 交换数组中两个元素的位置
*/
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
二、堆的定义与性质
最大堆（Max Heap） 满足以下性质：对于任意节点 i，其值大于或等于左右子节点的值。即 arr[i] >= arr[left(i)] 且 arr[i] >= arr[right(i)]。这意味着堆顶（索引 0）始终是整个数组中的最大值。
最小堆（Min Heap） 则相反：父节点的值小于或等于子节点，堆顶为最小值。
堆排序使用最大堆，通过反复将堆顶元素移到数组末尾，逐步完成排序。
三、核心操作：下沉（Sift Down）
下沉操作是堆排序的灵魂。假设某个节点 i 的值小于其子节点，违反了最大堆性质，我们需要将它”下沉”到合适的位置，直到重新满足堆性质。
/**
* 最大堆的核心类
* 支持建堆、下沉、上浮操作
*/
public class MaxHeap {
private final int[] data; // 底层数组
private int size; // 当前堆中有效元素个数
public MaxHeap(int[] arr) {
// 复制数组，避免修改原始输入
this.data = new int[arr.length];
System.arraycopy(arr, 0, this.data, 0, arr.length);
this.size = arr.length;
// 建堆：从最后一个非叶子节点开始，逐个下沉
buildHeap();
}
/**
* 建堆：O(n) 时间复杂度
* 从最后一个非叶子节点（size/2 - 1）开始向前遍历，对每个节点执行下沉
*/
private void buildHeap() {
for (int i = size / 2 - 1; i >= 0; i--) {
siftDown(i);
}
}
/**
* 下沉操作：将节点i下沉到合适位置，恢复最大堆性质
* 时间复杂度：O(log n)
*/
public void siftDown(int i) {
while (true) {
int largest = i;
int left = HeapUtils.left(i);
int right = HeapUtils.right(i);
// 与左子节点比较
if (left < size && data[left] > data[largest]) {
largest = left;
}
// 与右子节点比较
if (right < size && data[right] > data[largest]) {
largest = right;
}
// 如果当前节点已经是最大的，下沉结束
if (largest == i) {
break;
}
// 交换当前节点与较大的子节点
HeapUtils.swap(data, i, largest);
i = largest; // 继续向下检查
}
}
/**
* 上浮操作：将节点i上浮到合适位置
* 用于插入新元素时维护堆性质
*/
public void siftUp(int i) {
while (i > 0) {
int parent = HeapUtils.parent(i);
if (data[i] <= data[parent]) {
break; // 已满足堆性质
}
HeapUtils.swap(data, i, parent);
i = parent;
}
}
/**
* 提取堆顶元素（最大值），并用最后一个元素填补
* 然后对新的堆顶执行下沉
*/
public int extractMax() {
if (size == 0) {
throw new IllegalStateException("堆为空");
}
int max = data[0];
data[0] = data[size - 1]; // 用最后一个元素替换堆顶
size--;
if (size > 0) {
siftDown(0); // 新的堆顶可能违反堆性质，需要下沉
}
return max;
}
/**
* 获取当前堆顶元素，不移除
*/
public int peek() {
if (size == 0) {
throw new IllegalStateException("堆为空");
}
return data[0];
}
/**
* 获取当前堆大小
*/
public int getSize() {
return size;
}
/**
* 获取内部数组（用于堆排序时读取排序结果）
*/
public int[] getData() {
return data;
}
}
四、堆排序完整实现
堆排序分为两个阶段：
- 建堆：将无序数组构造成最大堆，O(n)
- 排序：反复提取最大值并放到数组末尾，同时缩小堆的范围，O(n log n)
/**
* 堆排序算法完整实现
* 时间复杂度：最坏/平均/最好均为 O(n log n)
* 空间复杂度：O(1)，原地排序
* 稳定性：不稳定排序
*/
public class HeapSort {
/**
* 对外接口：对数组进行升序堆排序
*/
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 阶段一：建堆（原地构建最大堆）
// 从最后一个非叶子节点开始向前遍历
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(arr, n, i);
}
// 阶段二：排序
// 将堆顶（最大值）与末尾元素交换，然后对剩余部分重新堆化
for (int end = n - 1; end > 0; end--) {
// 将当前最大值放到正确位置
HeapUtils.swap(arr, 0, end);
// 对缩减后的堆（0 到 end-1）重新堆化
siftDown(arr, end, 0);
}
}
/**
* 原地下沉操作（排序专用版本）
* @param arr 目标数组
* @param size 当前堆的有效大小
* @param i 需要下沉的节点索引
*/
private static void siftDown(int[] arr, int size, int i) {
while (true) {
int largest = i;
int left = HeapUtils.left(i);
int right = HeapUtils.right(i);
if (left < size && arr[left] > arr[largest]) {
largest = left;
}
if (right < size && arr[right] > arr[largest]) {
largest = right;
}
if (largest == i) {
break;
}
HeapUtils.swap(arr, i, largest);
i = largest;
}
}
}
五、为什么建堆是 O(n)？
一个常见的误解是认为建堆的时间复杂度是 O(n log n)，因为要对 n/2 个节点各做一次 O(log n) 的下沉。但实际上，大部分节点位于堆的底层，它们的下沉深度非常有限。
设在高度为 h 的层上最多有 ceil(n / 2^(h+1)) 个节点，每个节点最多下沉 h 层。总时间为：
T(n) = sum(h=0 to log n) [ ceil(n / 2^(h+1)) * O(h) ]
= O(n * sum(h=0 to inf) h / 2^h )
由于 sum(h=0 to inf) h / 2^h = 2，因此 T(n) = O(n)。这是一个优美的结论：建堆的线性复杂度使得堆排序的整体效率非常有竞争力。
六、完整测试与验证
public class Main {
public static void main(String[] args) {
// 测试用例1：随机数组
int[] arr1 = {64, 34, 25, 12, 22, 11, 90, 5, 77, 30};
testSort("随机数组", arr1);
// 测试用例2：已排序数组（最坏情况对快排而言，但堆排序仍 O(n log n)）
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
testSort("已排序数组", arr2);
// 测试用例3：逆序数组
int[] arr3 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
testSort("逆序数组", arr3);
// 测试用例4：大量重复元素
int[] arr4 = {5, 5, 5, 1, 1, 3, 3, 3, 3, 2};
testSort("重复元素", arr4);
// 测试用例5：单元素
int[] arr5 = {42};
testSort("单元素", arr5);
// 测试用例6：空数组
int[] arr6 = {};
testSort("空数组", arr6);
// 测试 MaxHeap 的独立功能
System.out.println("\n=== MaxHeap 独立测试 ===");
int[] heapData = {3, 1, 4, 1, 5, 9, 2, 6};
MaxHeap heap = new MaxHeap(heapData);
System.out.print("依次提取最大值: ");
while (heap.getSize() > 0) {
System.out.print(heap.extractMax() + " ");
}
System.out.println();
}
private static void testSort(String name, int[] arr) {
int[] copy = arr.clone();
HeapSort.sort(copy);
boolean sorted = isSorted(copy);
System.out.printf("[%s] %s -> %s%n",
sorted ? "PASS" : "FAIL",
name,
arrayToString(copy));
}
private static boolean isSorted(int[] arr) {
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
return false;
}
}
return true;
}
private static String arrayToString(int[] arr) {
if (arr.length == 0) return "[]";
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < arr.length; i++) {
sb.append(arr[i]);
if (i < arr.length - 1) sb.append(", ");
}
sb.append("]");
return sb.toString();
}
}
运行结果：
[PASS] 随机数组 -> [5, 11, 12, 22, 25, 30, 34, 64, 77, 90]
[PASS] 已排序数组 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[PASS] 逆序数组 -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[PASS] 重复元素 -> [1, 1, 2, 3, 3, 3, 3, 5, 5, 5]
[PASS] 单元素 -> [42]
[PASS] 空数组 -> []
=== MaxHeap 独立测试 ===
依次提取最大值: 9 6 5 4 3 2 1 1
七、实战应用：Top K 问题
堆排序的思想可以直接用于解决经典的 Top K 问题：从 n 个元素中找出最大的 K 个。
使用最小堆维护当前最大的 K 个元素：遍历数组时，若当前元素大于堆顶，则替换堆顶并重新堆化。最终堆中即为所求。
import java.util.Arrays;
/**
* 基于最小堆的 Top K 查找
* 时间复杂度：O(n log k)，当 k << n 时效率极高
*/
public class TopKFinder {
/**
* 查找数组中最大的k个元素
* @param arr 输入数组
* @param k 需要查找的元素个数
* @return 最大的k个元素（无序）
*/
public static int[] findTopK(int[] arr, int k) {
if (k <= 0) {
return new int[0];
}
if (k >= arr.length) {
return arr.clone();
}
// 用前k个元素构建最小堆
int[] heap = new int[k];
System.arraycopy(arr, 0, heap, 0, k);
buildMinHeap(heap);
// 遍历剩余元素
for (int i = k; i < arr.length; i++) {
if (arr[i] > heap[0]) {
// 当前元素比堆顶大，替换堆顶
heap[0] = arr[i];
siftDownMin(heap, k, 0);
}
}
return heap;
}
private static void buildMinHeap(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
siftDownMin(arr, n, i);
}
}
/**
* 最小堆下沉：父节点小于等于子节点
*/
private static void siftDownMin(int[] arr, int size, int i) {
while (true) {
int smallest = i;
int left = HeapUtils.left(i);
int right = HeapUtils.right(i);
if (left < size && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < size && arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest == i) {
break;
}
HeapUtils.swap(arr, i, smallest);
i = smallest;
}
}
public static void main(String[] args) {
int[] data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int k = 3;
int[] topK = findTopK(data, k);
Arrays.sort(topK); // 仅用于展示，输出排序后的结果
System.out.println("Top " + k + ": " + Arrays.toString(topK));
// 输出: Top 3: [5, 6, 9]
}
}
八、复杂度总结与适用场景
| 指标 | 堆排序 | 快速排序 | 归并排序 |
|---|---|---|---|
| 平均时间复杂度 | O(n log n) | O(n log n) | O(n log n) |
| 最坏时间复杂度 | O(n log n) | O(n²) | O(n log n) |
| 空间复杂度 | O(1) | O(log n) | O(n) |
| 稳定性 | 不稳定 | 不稳定 | 稳定 |
堆排序的核心优势在于最坏情况保证和原地排序。当内存受限或对最坏性能有严格要求时（如嵌入式系统、实时数据处理），堆排序是理想选择。此外，堆结构本身在任务调度（如 Java 的 PriorityQueue）、图算法（如 Dijkstra 最短路径）中都有广泛应用，掌握堆排序就是掌握了这些高级算法的基石。
