一、啥是堆排序和完全二叉树
咱先说说堆排序，它是一种排序算法，能把一堆数据按照从小到大或者从大到小的顺序排好。而完全二叉树呢，是一种特殊的树结构，就像一个规整的金字塔，除了最下面一层，其他层的节点都是满的，最下面一层的节点也是从左到右依次排列。
堆排序就是利用完全二叉树的特性来实现高效排序的。堆其实就是一种特殊的完全二叉树，它分为大顶堆和小顶堆。大顶堆就是每个节点的值都大于或等于它的子节点的值；小顶堆则是每个节点的值都小于或等于它的子节点的值。
二、堆排序的基本原理
堆排序的基本思路是先把要排序的数据构建成一个堆，然后不断地把堆顶元素（也就是最大值或者最小值）取出来，放到合适的位置，再重新调整堆，直到所有元素都排好序。
举个例子，假如我们有一个数组 [4, 10, 3, 5, 1]，我们要把它从小到大排序。
三、具体实现步骤
1. 构建初始堆
我们先把数组看成一个完全二叉树，然后从最后一个非叶子节点开始，依次调整每个节点，让它满足堆的性质。
下面是用 Java 实现的构建初始堆的代码：
// Java 技术栈
public class HeapSort {
// 调整堆的方法
public static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化根节点为最大值
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比根节点大
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点比当前最大值大
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调整受影响的子树
heapify(arr, n, largest);
}
}
// 构建初始堆
public static void buildHeap(int[] arr) {
int n = arr.length;
// 从最后一个非叶子节点开始调整
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
}
}
在这个代码中，heapify 方法用于调整一个节点，让它满足堆的性质。buildHeap 方法则是从最后一个非叶子节点开始，依次调用 heapify 方法，构建初始堆。
2. 排序过程
构建好初始堆后，我们把堆顶元素（也就是最大值）和最后一个元素交换位置，然后把堆的大小减 1，再重新调整堆，重复这个过程，直到堆的大小为 1。
下面是完整的堆排序代码：
// Java 技术栈
public class HeapSort {
// 调整堆的方法
public static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化根节点为最大值
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比根节点大
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点比当前最大值大
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调整受影响的子树
heapify(arr, n, largest);
}
}
// 构建初始堆
public static void buildHeap(int[] arr) {
int n = arr.length;
// 从最后一个非叶子节点开始调整
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
}
// 堆排序方法
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建初始堆
buildHeap(arr);
// 一个个交换元素
for (int i = n - 1; i > 0; i--) {
// 把堆顶元素（最大值）和最后一个元素交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新调整堆
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
heapSort(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
在这个代码中，heapSort 方法实现了完整的堆排序过程。首先调用 buildHeap 方法构建初始堆，然后通过循环把堆顶元素和最后一个元素交换，再重新调整堆，直到所有元素都排好序。
四、应用场景
堆排序在很多场景下都很有用。比如在处理大数据时，需要对大量数据进行排序，堆排序的时间复杂度是 $O(n log n)$，效率比较高。另外，在一些需要动态维护数据的场景中，比如优先队列，堆排序也非常合适。
五、技术优缺点
优点
- 效率高：堆排序的平均时间复杂度和最坏时间复杂度都是 $O(n log n)$，在处理大规模数据时表现不错。
- 空间复杂度低：只需要常数级的额外空间，不需要像归并排序那样需要额外的数组来存储中间结果。
缺点
- 不稳定：堆排序是一种不稳定的排序算法，也就是说，相等元素的相对顺序可能会改变。
- 实现复杂：相比一些简单的排序算法，堆排序的实现要复杂一些，理解起来也需要一定的时间。
六、注意事项
- 堆的调整：在调整堆的过程中，要注意递归调用
heapify方法，确保堆的性质得到维护。 - 边界条件：在处理数组下标时，要注意边界条件，避免越界错误。
七、文章总结
堆排序是一种利用完全二叉树特性实现的高效排序算法。它通过构建初始堆，然后不断交换堆顶元素和最后一个元素，再重新调整堆，最终实现排序。堆排序的时间复杂度是 $O(n log n)$，空间复杂度是 $O(1)$，适用于处理大规模数据。虽然它有一些缺点，比如不稳定和实现复杂，但在很多场景下还是非常有用的。
评论