数据结构第22节 堆排序优化
堆排序是一种基于比较的排序算法，其核心是使用一种叫做“堆”的数据结构。堆通常是一个完全二叉树的数组表示，在数组中可以快速找到最大值或最小值。堆排序可以分为两种类型：最大堆和最小堆。
在最大堆中，父节点的键始终大于或等于任何子节点的键。在最小堆中，情况则相反，父节点的键始终小于或等于任何子节点的键。堆排序通常使用最大堆进行降序排序，或者使用最小堆进行升序排序。
以下是使用Java实现堆排序的基本步骤：
-
构建最大堆：
- 将输入数组视为一个完全二叉树的数组表示。
- 从最后一个非叶子节点开始（即
array.length / 2 - 1），对每个节点应用下沉操作，以确保其满足最大堆的性质。
-
排序：
- 将堆顶元素（最大值）与堆末尾的元素交换，减少堆的大小，并将新的堆顶元素下沉，使其再次满足最大堆的性质。
- 重复此过程，直到堆的大小减少到1。
下面是一个具体的Java代码示例来实现堆排序：
public class HeapSort {public static void heapSort(int[] array) {// Build heap (rearrange array)for (int i = array.length / 2 - 1; i >= 0; i--) {heapify(array, array.length, i);}// One by one extract an element from heapfor (int i = array.length - 1; i > 0; i--) {// Move current root to endint temp = array[0];array[0] = array[i];array[i] = temp;// call max heapify on the reduced heapheapify(array, i, 0);}}// To heapify a subtree rooted with node i which is an index in array[]private static void heapify(int[] array, int heapSize, int i) {int largest = i; // Initialize largest as rootint leftChild = 2 * i + 1; // left childint rightChild = 2 * i + 2; // right child// If left child is larger than rootif (leftChild < heapSize && array[leftChild] > array[largest]) {largest = leftChild;}// If right child is larger than largest so farif (rightChild < heapSize && array[rightChild] > array[largest]) {largest = rightChild;}// If largest is not rootif (largest != i) {int swap = array[i];array[i] = array[largest];array[largest] = swap;// Recursively heapify the affected sub-treeheapify(array, heapSize, largest);}}
}
在这个例子中，heapSort函数首先通过调用heapify函数建立一个最大堆，然后将堆顶元素与堆的最后一个元素交换，减少堆的大小，并重新调整剩余元素以保持最大堆的性质。这样重复直到整个数组排序完成。
为了进一步优化堆排序的代码，我们可以考虑以下几点：
-
内联小函数：如果
heapify函数很小且频繁调用，可以考虑将其内联到heapSort函数中，以减少函数调用的开销。 -
减少数组访问：在
heapify函数中，多次访问array中的元素可能会导致缓存未命中，从而影响性能。我们可以通过缓存一些频繁访问的值来减少这种影响。 -
边界条件检查：确保在循环中检查边界条件，避免不必要的计算。
-
使用循环展开：对于某些循环，使用循环展开可以减少循环控制结构的开销。
-
尾递归优化：如果使用了递归的
heapify，可以尝试将其转换为迭代版本，因为JVM可能不支持尾递归优化。
下面是一个经过微调的堆排序实现，其中heapify函数被内联并进行了数组访问优化：
public class HeapSortOptimized {public static void heapSort(int[] array) {int n = array.length;// Build heapfor (int i = n / 2 - 1; i >= 0; i--) {int largest = i;int leftChild = 2 * i + 1;int rightChild = 2 * i + 2;if (leftChild < n && array[leftChild] > array[largest]) {largest = leftChild;}if (rightChild < n && array[rightChild] > array[largest]) {largest = rightChild;}if (largest != i) {int temp = array[i];array[i] = array[largest];array[largest] = temp;// Recursively heapify the affected sub-treei = largest;leftChild = 2 * i + 1;rightChild = 2 * i + 2;while (leftChild < n) {largest = i;if (array[leftChild] > array[largest]) {largest = leftChild;}if (rightChild < n && array[rightChild] > array[largest]) {largest = rightChild;}if (largest == i) {break;}temp = array[i];array[i] = array[largest];array[largest] = temp;i = largest;leftChild = 2 * i + 1;rightChild = 2 * i + 2;}}}// Extract elements one by onefor (int i = n - 1; i > 0; i--) {int temp = array[0];array[0] = array[i];array[i] = temp;int j = 0;int leftChild = 1;int rightChild = 2;while (leftChild < i) {int largest = j;if (array[leftChild] > array[largest]) {largest = leftChild;}if (rightChild < i && array[rightChild] > array[largest]) {largest = rightChild;}if (largest == j) {break;}temp = array[j];array[j] = array[largest];array[largest] = temp;j = largest;leftChild = 2 * j + 1;rightChild = 2 * j + 2;}}}
}
这个优化版本中，heapify逻辑被直接整合到了heapSort函数中，并且在每次交换后都检查是否需要继续下沉，以避免不必要的额外工作。此外，数组元素的频繁访问被优化，减少了不必要的内存读取。但是，值得注意的是，过度优化可能会影响代码的可读性和维护性，因此在实际开发中需要权衡利弊。
堆排序的过程可以分为两个主要阶段：构建最大堆和排序。我将以一个简单的示例数组 [4, 10, 3, 5, 1] 来逐步说明堆排序的过程，并使用表格形式展示每一步的变化。
第一阶段：构建最大堆
-
初始状态:
| Index | Value | |-------|-------| | 0 | 4 | | 1 | 10 | | 2 | 3 | | 3 | 5 | | 4 | 1 | -
从最后一个非叶节点开始下沉:
- 节点 1 (值 10) 是最后一个非叶节点。
- 节点 1 已经是最大堆的一部分，无需调整。
-
节点 0 下沉:
- 节点 0 (值 4) 有子节点 1 (值 10) 和 2 (值 3)，其中最大的是子节点 1。
- 交换节点 0 和节点 1 的值。
| Index | Value | |-------|-------| | 0 | 10 | | 1 | 4 | | 2 | 3 | | 3 | 5 | | 4 | 1 |- 节点 0 现在是值 10，它没有子节点比它大，所以不需要进一步调整。
现在，我们有一个最大堆:
| Index | Value |
|-------|-------|
| 0 | 10 |
| 1 | 4 |
| 2 | 3 |
| 3 | 5 |
| 4 | 1 |
第二阶段：排序
-
交换堆顶元素与最后一个元素:
- 交换节点 0 (值 10) 和节点 4 (值 1)。
| Index | Value | |-------|-------| | 0 | 1 | | 1 | 4 | | 2 | 3 | | 3 | 5 | | 4 | 10 |- 减少堆的大小，不再考虑索引 4。
-
调整堆:
- 节点 0 (值 1) 需要下沉。
- 交换节点 0 和节点 3 (值 5)。
| Index | Value | |-------|-------| | 0 | 5 | | 1 | 4 | | 2 | 3 | | 3 | 1 | | 4 | 10 |- 节点 0 现在是值 5，它没有子节点比它大，所以不需要进一步调整。
-
再次交换堆顶元素与最后一个元素:
- 交换节点 0 (值 5) 和节点 3 (值 1)。
| Index | Value | |-------|-------| | 0 | 1 | | 1 | 4 | | 2 | 3 | | 3 | 5 | | 4 | 10 |- 减少堆的大小，不再考虑索引 3。
-
调整堆:
- 节点 0 (值 1) 需要下沉。
- 由于节点 0 没有子节点，不需要进一步调整。
重复以上步骤，直到堆的大小减至 1。
最终排序结果:
| Index | Value |
|-------|-------|
| 0 | 1 |
| 1 | 3 |
| 2 | 4 |
| 3 | 5 |
| 4 | 10 |
这就是堆排序的完整过程，通过构建最大堆和不断交换并调整堆，最后得到一个有序的数组。