【算法-堆排序】

堆排序是一种基于堆这种数据结构的比较排序算法，它是一种原地、不稳定的排序算法，时间复杂度为 O(n log n)。堆排序的基本思想是将数组构建成一个二叉堆，并通过反复调整堆顶和未排序部分之间的关系来实现排序。

堆的定义

堆是一种特殊的完全二叉树，分为最大堆和最小堆：

• 最大堆：每个节点的值都大于或等于其子节点的值，堆顶为最大值。
• 最小堆：每个节点的值都小于或等于其子节点的值，堆顶为最小值。
  在堆排序中，通常使用最大堆来进行升序排序。

完全二叉树

堆结构基于完全二叉树（所有层的节点均填满，且最下层的节点靠左排列），通过数组来表示堆，每个节点的索引关系为：

• 父节点：(i - 1) / 2
• 左子节点：2 * i + 1
• 右子节点：2 * i + 2

堆排序的原理

堆排序基于最大堆的特性：

• 最大堆的堆顶是整个数组的最大值。
• 通过构建最大堆，将最大值与数组的末尾元素交换，此时堆的大小减少1，排除掉已排好的最大值。
• 调整剩余的堆，使其继续满足最大堆的性质，重复上述过程，最终得到有序数组。

堆排序的步骤

堆排序分为两个阶段：

• 构建最大堆：
  从最后一个非叶子节点开始，向上调整每个子树，使其满足最大堆的性质。
• 排序：
  将堆顶元素与堆的最后一个元素交换，然后对剩余的元素继续调整为最大堆。每次将最大值放在数组的末尾。

Java代码实现

   public class HeapSort {// 主函数：堆排序算法public void heapSort(int[] arr) {int n = arr.length;// 1. 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 2. 一个个将最大值交换到末尾并调整堆for (int i = n - 1; i > 0; i--) {// 将堆顶元素和末尾元素交换swap(arr, 0, i);// 调整堆，去掉已排序的元素heapify(arr, i, 0);}}// 调整堆的函数，确保以root为根的子树满足最大堆性质private void heapify(int[] arr, int n, int root) {int largest = root;int left = 2 * root + 1; // 左子节点int right = 2 * root + 2; // 右子节点// 如果左子节点比root节点大if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点比当前largest节点大if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果largest不是root，交换root和largestif (largest != root) {swap(arr, root, largest);// 递归地对受影响的子树进行堆调整heapify(arr, n, largest);}}// 辅助函数：交换数组中的两个元素private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 打印数组函数public static void printArray(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println();}// 测试堆排序public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6, 7};HeapSort heapSort = new HeapSort();System.out.println("原始数组:");printArray(arr);heapSort.heapSort(arr);System.out.println("排序后的数组:");printArray(arr);}
}

输出结果：

原始数组:
12 11 13 5 6 7 
排序后的数组:
5 6 7 11 12 13 

堆排序的时间和空间复杂度

时间复杂度：
构建最大堆：O(n)。
调整堆：每次调整堆的时间复杂度为 O(log n)，共进行 n 次调整。因此，堆排序的总体时间复杂度为 O(n log n)。

空间复杂度：
堆排序是原地排序算法，不需要额外的存储空间，空间复杂度为 O(1)。

堆排序的优缺点

优点

• 时间复杂度稳定：堆排序的时间复杂度始终为 O(n log n)，无论是最好、最坏还是平均情况。
• 空间复杂度低：堆排序是原地排序算法，空间复杂度为 O(1)，非常节省内存。
• 不依赖于输入数据的分布：堆排序对输入数据的初始状态不敏感，始终保证 O(n log n) 的时间复杂度。

缺点

• 不稳定：堆排序可能改变相同元素的相对顺序，因此它不是一个稳定的排序算法。
• 常数因子较高：堆排序在实际应用中的速度通常比快速排序稍慢，这是因为堆排序中的堆调整操作较复杂。

使用场景

• 需要稳定时间复杂度的场合：在无法预知输入数据分布，或输入数据最坏情况下其他算法（如快速排序）性能下降时，堆排序是一种保证 O(n log n) 时间复杂度的选择。
• 内存受限场景：堆排序的空间复杂度为 O(1)，因此在内存紧张的场景下非常有用。
• 优先队列的实现：堆结构常用于实现优先队列等数据结构。

总结

堆排序是一种稳定高效的排序算法，时间复杂度为 O(n log n)，空间复杂度为 O(1)，具有普遍适用的特点。虽然其不稳定性和相对较高的常数因子可能在某些应用中影响其表现，但在需要稳定时间复杂度和低内存消耗的场合下，堆排序仍然是一个理想的选择。