堆排序算法

什么是堆排序？

堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。它利用了完全二叉树的特性，将待排序的数据构造成一个最大堆或最小堆，然后通过不断移除堆顶元素并重新调整堆来实现排序。堆排序具有稳定的时间复杂度O(n log n)，并且不需要额外的空间，因此在处理大规模数据时表现良好。

二叉堆的概念

• 最大堆：每个节点的值都大于或等于其子节点的值。
• 最小堆：每个节点的值都小于或等于其子节点的值。

在堆排序中，通常使用最大堆来进行升序排序，使用最小堆进行降序排序。本文主要介绍基于最大堆的升序排序。

堆排序的基本步骤

1. 构建最大堆：

   • 将数组视为一个完全二叉树，并将其转换为最大堆。
   • 从最后一个非叶子节点开始（即 n/2 - 1），向上遍历每个节点，调用 heapify 函数来维护最大堆的性质。

2. 堆排序过程：

   • 将堆顶元素（最大值）与当前未排序部分的最后一个元素交换。
   • 缩小堆的大小（减少一个元素），并将新的堆顶元素向下调整以保持最大堆的性质。
   • 重复上述两步直到整个数组有序。

堆排序的详细流程

构建最大堆

构建最大堆的过程是从最后一个非叶子节点开始，逐层向上调整每个节点，确保它们满足最大堆的性质。

维护最大堆

heapify 函数用于维护最大堆的性质。如果发现某个节点不满足最大堆的条件，则交换该节点与其子节点中的较大者，并递归地继续调整子树。

排序过程

排序过程是通过不断将堆顶元素与当前未排序部分的最后一个元素交换，并缩小堆的大小，直到整个数组有序。

Java代码实现

java">public static void heapSort(int[] arr) {int n = arr.length;// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 将堆顶元素逐个取出，并从后向前放置到数组中for (int i = n - 1; i > 0; i--) {// 交换堆顶元素至最后一个无序位置swap(arr, 0, i);// 重新调整为最大堆heapify(arr, i, 0);}
}private static void heapify(int[] arr, int n, int i) {int largest = i;  // 使用根节点索引初始化int left = 2 * i + 1; // 左叶子节点索引int right = (i + 1) * 2; // 右叶子节点索引// 查找最大的元素if(left < n && arr[left] > arr[largest]) {largest = left;}if(right < n && arr[right] > arr[largest]) {largest = right;}// 如果根节点不是最大值if(largest != i) {// 交换根节点和最大值节点swap(arr, i, largest);// 对子树递归堆化heapify(arr, n, largest);}
}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

堆排序的图示步骤

这里以数组[3, 8, 6, 9, 2, 1, 5, 4, 7]升序排序，使用最大堆演示排序过程，具体步骤如下：

1. 初始的数组与堆

堆排序是利用完全二叉树进行排序的，内存中实际保存的是数组，但程序中的逻辑结构是一棵完全二叉树，如上图。

2. 构建最大堆

2.1. 检查节点9（序号为3）

从最后一个非叶子节点9（序号为3）开始检查，依次构造最大堆。

数组长度为n = arr.length = 9，第一个非叶子节点序号为i = n / 2 - 1 = 3。
节点9的左右节点序号分别为2 * i + 1和(i + 1) * 2，即7和8，它们的值分别为4和7。由于9>4,9>7，所以节点9符合最大堆的特性，无需调整。

2.2. 检查节点6（序号为2）

i–,值变为2，检查序号为2的节点。

其左右节点的序号分别为2 * i + 1和(i + 1) * 2，即5和6，它们的值分别为1和5。由于6>1,6>5，所以节点6符合最大堆的特性，也无需调整。

2.3. 检查节点8（序号为1）

i–,值变为1，检查序号为1的节点。

其左右节点的序号分别为3和4，它们的值分别为9和2。由于8<9，所以交换节点8和9。

交换完成后，由于节点序号为3的元素值减小，以此为根的子树有可能违反最大堆的特性，所以递归检查该节点。

由于8>4且8>7，所以该子树符合最大堆特点。

2.4. 检查节点3（序号为0）

i–,值变为0，检查序号为0的节点。

其左右节点的序号分别为1和2，它们的值分别为9和6。由于3<9，所以交换节点3和9。

交换完成后，由于节点序号为1的元素值减小，以此为根的子树有可能违反最大堆的特性，所以递归检查该节点。

交换完成后，由于节点序号为3的元素值减小，以此为根的子树有可能违反最大堆的特性，继续递归检查该节点。

2.5. 完成堆构造

i–,值变为-1，循环结束。至此最大堆构造完成。

3. 归位

3.1 归位索引8

将堆顶元素逐个取出，并从后向前放置到数组进行归位。

将堆顶元素9与索引为8的元素交换位置，元素9完成排序，从堆中移除（虚线表示）。
交换完成后，由于节点序号为0的元素值减小，以此为根的子树有可能违反最大堆的特性，继续递归检查该节点。

交换序号分别为0和1的节点元素，并继续递归检查序号为1的节点。

交换序号分别为1和3的节点元素，并继续递归检查序号为3的节点。

至此，剩余8个元素恢复为最大堆。

3.2 归位索引7

将堆顶元素8与索引为7的元素交换位置，元素8完成排序，从堆中移除（虚线表示）。
交换完成后，由于节点序号为0的元素值减小，以此为根的子树有可能违反最大堆的特性，继续递归检查该节点。

交换序号分别为0和1的节点元素，并继续递归检查序号为3的节点。

交换序号分别为1和3的节点元素，并继续递归检查序号为3的节点。3号节点为叶子节点，无须调整。
至此，剩余7个元素恢复为最大堆。

3.3 归位索引6

将堆顶元素7与索引为6的元素交换位置，元素7完成排序，从堆中移除（虚线表示）。
交换完成后，由于节点序号为0的元素值减小，以此为根的子树有可能违反最大堆的特性，继续递归检查该节点。

交换序号分别为0和2的节点元素，并继续递归检查序号为2的节点。

2号节点符合最大堆特点，无须调整。
至此，剩余6个元素恢复为最大堆。

3.4 归位索引5

将堆顶元素6与索引为5的元素交换位置，元素6完成排序，从堆中移除（虚线表示）。
交换完成后，由于节点序号为0的元素值减小，以此为根的子树有可能违反最大堆的特性，继续递归检查该节点。

交换序号分别为0和2的节点元素，并继续递归检查序号为2的节点。

2号节点为叶子节点，无须调整。
至此，剩余5个元素恢复为最大堆。

3.5 归位索引4

将堆顶元素5与索引为4的元素交换位置，元素5完成排序，从堆中移除（虚线表示）。
交换完成后，由于节点序号为0的元素值减小，以此为根的子树有可能违反最大堆的特性，继续递归检查该节点。

交换序号分别为0和1的节点元素，并继续递归检查序号为1的节点。

交换序号分别为1和3的节点元素，并继续递归检查序号为3的节点。

3号节点为叶子节点，无须调整。
至此，剩余4个元素恢复为最大堆。

3.6 归位索引3

将堆顶元素4与索引为3的元素交换位置，元素4完成排序，从堆中移除（虚线表示）。
交换完成后，由于节点序号为0的元素值减小，以此为根的子树有可能违反最大堆的特性，继续递归检查该节点。

交换序号分别为0和1的节点元素，并继续递归检查序号为1的节点。

1号节点为叶子节点，无须调整。
至此，剩余3个元素恢复为最大堆。

3.7 归位索引2

将堆顶元素3与索引为2的元素交换位置，元素3完成排序，从堆中移除（虚线表示）。
交换完成后，由于节点序号为0的元素值减小，以此为根的子树有可能违反最大堆的特性，继续递归检查该节点。

交换序号分别为0和1的节点元素，并继续递归检查序号为1的节点。

1号节点为叶子节点，无须调整。
至此，剩余2个元素恢复为最大堆。

3.8 归位索引1

将堆顶元素2与索引为1的元素交换位置，元素2完成排序，从堆中移除（虚线表示）。
交换完成后，由于节点序号为0的元素值减小，以此为根的子树有可能违反最大堆的特性，继续递归检查该节点。

0号节点为叶子节点，无须调整。
至此，剩余1个元素恢复为最大堆。

3.9 归位索引0

将堆顶元素1与索引为0的元素交换位置，元素1完成排序，从堆中移除（虚线表示）。

至此，循环结束，递归也结束，排序完成。

时间复杂度和空间复杂度

• 时间复杂度：
  • 构建堆的时间复杂度是 O(n)。
  • 每次提取堆顶元素并重新调整堆的时间复杂度是 O(log n)，总共需要进行 n 次这样的操作。
  • 因此，总的时间复杂度为 O(n log n)。
• 空间复杂度：
  • 堆排序是一个原地排序算法，只需要常数级别的额外空间 O(1)。

特点和适用场景

优点

• 稳定性：虽然堆排序不是稳定的排序算法，但它的时间复杂度在最坏情况下也是 O(n log n)，这使得它在处理大规模数据时非常高效。
• 空间效率高：由于它是原地排序算法，不需要额外的存储空间。

缺点

性能略逊于快速排序：尽管堆排序的时间复杂度是 O(n log n)，但在实际应用中，它的常数因子较大，导致其运行速度可能比快速排序慢。

适用场景

当你需要一种稳定的时间复杂度 O(n log n) 的排序算法，并且内存占用要求较高时，堆排序是一个不错的选择。

结语

堆排序作为一种经典的排序算法，不仅在理论上有重要的意义，在实际应用中也经常被使用。理解堆排序的工作原理及其背后的二叉堆数据结构，有助于更好地掌握其他高级算法和数据结构。