堆与堆排序：大根堆的实现
从完全二叉树和大根堆的性质出发，整理建堆、堆调整与堆排序的实现思路。
在计算机科学中，排序算法是基础且至关重要的一环。其中，堆排序（Heap Sort）是一种高效的、基于比较的排序算法。要深入理解堆排序，我们首先必须掌握其核心数据结构——堆（Heap）。本文将从大根堆的实现细节入手，逐步过渡到两种不同建堆策略的堆排序算法。
一、核心数据结构：大根堆（Max Heap）
堆在逻辑上是一种完全二叉树，物理上则通常用数组来实现。根据其性质可分为大根堆和小根堆。
大根堆的两个核心性质：
- 它必须是一棵完全二叉树。
- 任意节点的值都必须大于或等于其子节点的值。
这意味着，大根堆的根节点一定是整个堆中的最大值。基于此特性，我们可以实现一个优先队列等结构。
1.1 大根堆的基本结构
我们使用一个数组来存储堆的元素，并需要几个变量来管理堆的状态：
heap: 用于存储元素的数组。heapsize: 当前堆中包含的元素数量。limit: 堆的最大容量。
java
public class MaxHeap {
private int[] heap;
private int heapsize;
private int limit;
public MaxHeap(int limit) {
heap = new int[limit];
heapsize = 0;
this.limit = limit;
}
public boolean isEmpty() {
return heapsize == 0;
}
public boolean isFull() {
return heapsize == limit;
}
// ... 其他方法
}
1.2 入堆操作：push 与 heapInsert
向堆中添加一个新元素时，我们首先将其放置在数组的末尾（即完全二叉树的下一个可用位置），然后通过一个“向上调整”的过程（heapInsert）来维持大根堆的性质。
heapInsert 的核心思路：将新加入的节点（idx 位置）与其父节点（(idx - 1) / 2 位置）进行比较。如果子节点的值大于父节点，则交换它们的位置，并继续向上比较，直到该节点不再大于其父节点，或已到达堆顶。
下面的代码展示了 push 和 heapInsert 的实现。
java
public void push(int val) {
if (isFull()) {
return;
}
heap[heapsize++] = val;
heapInsert(heap, heapsize - 1);
}
public void heapInsert(int[] arr, int idx) {
while (arr[idx] > arr[(idx - 1) / 2]) {
swap(arr, idx, (idx - 1) / 2);
idx = (idx - 1) / 2;
}
}
public void swap (int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
1.3 出堆操作：pop 与 heapify
从大根堆中弹出元素，实际上是取出堆顶的最大值。为了保持堆的结构，我们不能简单地移除根节点。标准操作如下：
- 记录堆顶（
0位置）的元素作为返回值。 - 将堆的最后一个元素与堆顶元素交换。
- 将堆的大小（
heapsize）减一。 - 对新的堆顶元素执行“向下调整”（
heapify）操作，以恢复大根堆的性质。
heapify 的核心思路：从指定节点（idx 位置）开始，比较它和它的左右子节点（左子节点：2*idx + 1，右子节点：2*idx + 2）的值。找出三者中的最大值。如果当前节点不是最大值，则将其与较大的子节点交换，并继续向下调整，直到该节点大于其所有子节点，或成为叶子节点。
java
public int pop() {
if (isEmpty()) {
throw new RuntimeException("堆是空的！");
}
int rst = heap[0];
swap(heap, 0, --heapsize);
heapify(heap, 0);
return rst;
}
public void heapify(int[] arr, int idx) {
int left = idx * 2 + 1;
while (left < heapsize) {
int right = left + 1;
int childMax = right < heapsize && arr[right] > arr[left] ? right : left;
int finalMax = arr[childMax] > arr[idx] ? childMax : idx;
if (finalMax == idx) {
break;
}
swap(heap, idx, finalMax);
idx = finalMax;
left = idx * 2 + 1;
}
}
二、堆排序（Heap Sort）
掌握了大根堆的 heapInsert 和 heapify 操作后，我们就可以轻松理解堆排序了。堆排序主要分为两个阶段：
- 建堆：将待排序的数组原地构建成一个大根堆。
- 排序：循环执行以下操作，直到堆大小为0。
a. 将堆顶元素（当前最大值）与堆末尾元素交换。
b. 将堆的大小减一，此时数组末尾的元素已经就位。
c. 对新的堆顶元素执行
heapify操作，以重新调整堆。
下面我们介绍两种建堆方式，它们分别对应了不同的时间复杂度。
2.1 方法一：自上而下建堆（时间复杂度 O(N log N)）
这种方法非常直观。我们遍历数组，依次将每个元素视为新加入的元素，并对其执行 heapInsert 操作。当遍历完成后，整个数组就构成了一个大根堆。
java
public void heapSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int heapsize = arr.length;
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, --heapsize);
heapify(arr, 0, heapsize);
}
}
2.2 方法二：自下而上建堆（时间复杂度 O(N)）
这是一种更优化的建堆方法。它放弃了逐个插入元素的思路，而是将整个数组预先看作一个完全二叉树，然后从最后一个非叶子节点开始，向前遍历至根节点，对每个节点执行 heapify 操作。
由于 heapify 的时间复杂度与树的高度相关，并且大部分节点的层数较低，通过数学证明可以得出，这种自下而上建堆的总时间复杂度为 $O(N)$，优于第一种方法。
建堆完成后，排序阶段的逻辑与方法一完全相同。
java
public void heapSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for(int i = arr.length - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
int heapsize = arr.length;
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, --heapsize);
heapify(arr, 0, heapsize);
}
}
三、完整实现与对数器验证
下面是堆排序的完整实现，包含了上述两种方法以及用于验证算法正确性的“对数器”（随机测试器）。对数器通过生成大量随机数组，并与系统内置的排序方法进行比对，来确保我们自己实现的算法是正确无误的，这是一种在算法开发中非常实用的测试手段。
java
package L6;
import java.util.Arrays;
import java.util.Random;
public class HeapSort {
public void heapSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int heapsize = arr.length;
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, --heapsize);
heapify(arr, 0, heapsize);
}
}
public void heapSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for(int i = arr.length - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
int heapsize = arr.length;
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, --heapsize);
heapify(arr, 0, heapsize);
}
}
public void heapInsert(int[] arr, int idx) {
while (arr[idx] > arr[(idx - 1) / 2]) {
swap(arr, idx ,(idx - 1) / 2);
idx = (idx - 1) / 2;
}
}
public void heapify(int[] arr, int idx, int heapsize) {
int left = idx * 2 + 1;
while (left < heapsize) {
int right = left + 1;
int childMax = right < heapsize && arr[right] > arr[left] ? right : left;
int finalMax = arr[childMax] > arr[idx] ? childMax : idx;
if (finalMax == idx) {
break;
}
swap(arr, idx, finalMax);
idx = finalMax;
left = idx * 2 + 1;
}
}
public void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
private static int[] generateRandomArray(int maxSize, int maxValue, Random r) {
int size = r.nextInt(maxSize + 1);
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = r.nextInt(maxValue + 1) - r.nextInt(maxValue + 1);
}
return arr;
}
private static int[] copyArray(int[] arr) {
if (arr == null) return null;
return Arrays.copyOf(arr, arr.length);
}
private static boolean isEqual(int[] a, int[] b) {
return Arrays.equals(a, b);
}
private static void comparator(int[] arr) {
Arrays.sort(arr);
}
private static void printArray(int[] arr) {
if (arr == null) {
System.out.println("null");
return;
}
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
HeapSort sorter = new HeapSort();
int testTime = 10000;
int maxSize = 50;
int maxValue = 100;
Random r = new Random();
boolean success = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue, r);
int[] arr2 = copyArray(arr1);
int[] arr3 = copyArray(arr1);
sorter.heapSort1(arr2);
sorter.heapSort2(arr3);
comparator(arr1);
if (!isEqual(arr1, arr2) || !isEqual(arr1, arr3)) {
success = false;
System.out.println("第" + i + "次测试失败！");
System.out.println("原数组: ");
printArray(arr1);
System.out.println("heapSort1结果: ");
printArray(arr2);
System.out.println("heapSort2结果: ");
printArray(arr3);
break;
}
}
System.out.println(success ? "Nice! 所有随机测试通过" : "有错误，请检查上面输出");
}
}