堆排序
堆排序就是利用堆的思想来对数据进行排序，其实主要就分为两个步骤，即建堆和堆的删除。
概念解惑
在正式介绍如何排序之前，先理清一些基本的操作，如什么时候用向上调整，什么时候用向下调整，以及分别在什么操作下对应什么位置来进行这些调整。
在堆排序中，构建大顶堆时确实使用向下调整（Heapify Down），但需要明确调整的起始点和调整方向的区别。
1. 向下调整（Heapify Down）的本质
-
调整方向：从某个节点向下与其子节点比较，确保父节点 ≥ 子节点（最大堆）。
-
起始点：构建堆时，从最后一个非叶子节点开始，自底向上遍历所有非叶子节点。
-
为什么是最后一个非叶子节点？
完全二叉树中，最后一个非叶子节点的下标为n/2 - 1（n是数组长度）。这些节点是“潜在不满足堆性质”的最小单元，调整它们可以高效构建堆。 -
处理顺序：从最后一个非叶子节点（最底层）向根节点方向逐个处理。
-
以这个二叉树为例子：
-
最后一个非叶子节点是值为
2的节点（下标2）。 -
调整顺序：先处理
2，再处理5，最后处理根节点3。
2. 向上调整（Heapify Up）的本质
-
调整方向：从某个节点（通常是新插入的叶子节点）向上与其父节点比较，确保子节点 ≤ 父节点（最大堆）。
-
起始点：插入新元素时，从新插入的叶子节点开始，逐步向上调整到根。
-
适用场景：适合动态插入元素到已有堆中（如优先队列）。
-
时间复杂度：每次插入需 O(log n) 时间，构建堆需 O(n log n)。
-
3. 代码对比：构建堆的两种方式
方式1：向下调整（正确且高效）
void buildMaxHeap(int arr[], int n) {
// 从最后一个非叶子节点开始，逆序处理所有非叶子节点
for (int i = n/2 - 1; i >= 0; i--) {
heapifyDown(arr, n, i); // 对每个非叶子节点向下调整
}
}//时间复杂度：O(n)
方式2：向上调整（低效，仅用于插入）
void buildMaxHeapWrong(int arr[], int n) {
// 错误示范：逐个插入元素，从叶子节点向上调整
for (int i = 0; i < n; i++) {
heapifyUp(arr, i); // 对每个新插入的节点向上调整
}
}//时间复杂度：O(n log n)（效率低，不推荐用于构建堆）
4.直观总结
这张图可以很好地概括这些问题：
5. 为什么构建堆不用向上调整？
-
数学证明：向下调整的时间复杂度为 O(n)，而向上调整需要 O(n log n)。
-
直观理解：叶子节点占总数的一半，调整叶子节点无意义（它们没有子节点）。向下调整从非叶子节点开始，减少了冗余操作。
堆排序原理
堆排序是一种高效的排序算法，利用二叉堆（通常为最大堆）数据结构实现。其核心思想是通过构建堆结构，反复提取最大元素并调整剩余部分，最终得到有序序列。
-
构建堆：将无序数组调整为最大堆（父节点值 ≥ 子节点值）（升序：建大堆 ，降序：建小堆）
-
排序阶段：
-
交换堆顶（最大值）与当前末尾元素。
-
缩小堆范围，重新调整剩余元素为最大堆。
-
重复上述步骤，直到所有元素有序。
-
简要实现（升序）
向下调整方法（递归版）
#include <stdio.h>// 交换元素
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 调整以i为根的子树为最大堆
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) {swap(&arr[i], &arr[largest]);heapify(arr, n, largest);}
}
堆排序
// 堆排序主函数
void heapSort(int arr[], int n) {// 构建最大堆（从最后一个非叶子节点开始）for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// 逐个提取元素for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]); // 将最大值移到末尾heapify(arr, i, 0); // 调整剩余部分为堆}
}
堆排序的适用场景
-
优点
-
时间复杂度稳定，始终为 O(nlogn)。
-
空间复杂度为O（1），适合内存有限的环境。
-
构建堆阶段：O(n)
排序阶段：O(n log n)
总时间复杂度：O(n) + O(n log n) = O(n log n)
无论是平均还是最坏情况，排序阶段的 O(n log n) 主导总时间复杂度，因此堆排序的时间复杂度稳定为 O(n log n)。
堆排序的时间复杂度与输入数据的初始顺序无关：
构建堆阶段：无论数据是否有序，都需要遍历所有非叶子节点调整。
排序阶段：每次提取堆顶后，必须从根节点向下调整，调整次数固定为树的高度（log n）。
因此，最坏情况与平均情况时间复杂度一致，均为 O(n log n)。
-
缺点
-
不是稳定的排序算法（相同的元素可能会改变相对顺序）。
-
对于小规模数据，可能不如插入排序等简单算法高效。
-
适用场景：
-
数据量较大且对稳定性要求不高的场景。
-
需要原地排序（不占用额外空间）的场景。
-
实时性要求较高的场景（如嵌入式系统、实时排序等）。
