目录
堆
在开始堆排序之前，我们需要先理解堆这种数据结构。
堆的定义
堆是一种特殊的完全二叉树，具有以下性质：
- 最大堆：每个父节点的值都大于或等于其子节点的值
- 最小堆：每个父节点的值都小于或等于其子节点的值
堆的数组表示
堆可以用数组来表示，对于索引为 i 的节点：
- 左子节点：2 * i + 1
- 右子节点：2 * i + 2
- 父节点：(i - 1) / 2
完全二叉树：
0
/ \
1 2
/ \ / \
3 4 5 6
数组表示：[A, B, C, D, E, F, G]
索引： [0, 1, 2, 3, 4, 5, 6]
堆排序算法思路
堆排序分为两个主要阶段：
- 构建堆：将无序数组构建成最大堆
- 排序：逐个提取堆顶元素（最大值），放到数组末尾
详细步骤演示
用一个具体的例子来演示堆排序的完整过程：
原始数组：[64, 34, 25, 12, 22, 11, 90]
数组索引：[ 0, 1, 2, 3, 4, 5, 6]第一步：构建最大堆
首先，将数组构建成最大堆。
1.1 找到最后一个非叶子节点
- 数组长度 n = 7
- 最后一个非叶子节点的索引 = (n/2) - 1 = (7/2) - 1 = 2
1.2 从最后一个非叶子节点开始，自底向上构建堆
处理索引2（值为25）：
当前状态：[64, 34, 25, 12, 22, 11, 90]
索引2的节点25：
- 左子节点：2*2+1=5，值为11
- 右子节点：2*2+2=6，值为90
比较：25 < 90，需要交换
交换后：[64, 34, 90, 12, 22, 11, 25]处理索引1（值为34）：
当前状态：[64, 34, 90, 12, 22, 11, 25]
索引1的节点34：
- 左子节点：2*1+1=3，值为12
- 右子节点：2*1+2=4，值为22
比较：34 > 12 且 34 > 22，无需交换
状态保持：[64, 34, 90, 12, 22, 11, 25]处理索引0（值为64）：
当前状态：[64, 34, 90, 12, 22, 11, 25]
索引0的节点64：
- 左子节点：2*0+1=1，值为34
- 右子节点：2*0+2=2，值为90
比较：64 < 90，需要交换
交换后：[90, 34, 64, 12, 22, 11, 25]
交换后需要重新调整索引2的子树：
索引2的节点64：
- 左子节点：2*2+1=5，值为11
- 右子节点：2*2+2=6，值为25
比较：64 > 11 且 64 > 25，无需交换
最终状态：[90, 34, 64, 12, 22, 11, 25]最大堆构建成功
第二步：排序过程
开始逐个提取堆顶元素（最大值）。
2.1 第一次提取
当前堆：[90, 34, 64, 12, 22, 11, 25]
堆顶元素：90（最大值）
将90与最后一个元素25交换：
[25, 34, 64, 12, 22, 11, 90]
现在90已经排好序，堆的大小减1
对剩余元素[25, 34, 64, 12, 22, 11]重新构建最大堆：
处理索引0（值为25）：
- 左子节点：34
- 右子节点：64
比较：25 < 64，交换
[64, 34, 25, 12, 22, 11, 90]
继续调整索引2（值为25）：
- 左子节点：11
- 右子节点：无
比较：25 > 11，无需交换
最终状态：[64, 34, 25, 12, 22, 11, 90]2.2 第二次提取
当前堆：[64, 34, 25, 12, 22, 11, 90]
堆顶元素：64（最大值）
将64与最后一个元素11交换：
[11, 34, 25, 12, 22, 64, 90]
对剩余元素[11, 34, 25, 12, 22]重新构建最大堆：
处理索引0（值为11）：
- 左子节点：34
- 右子节点：25
比较：11 < 34，交换
[34, 11, 25, 12, 22, 64, 90]
继续调整索引1（值为11）：
- 左子节点：12
- 右子节点：22
比较：11 < 22，交换
[34, 22, 25, 12, 11, 64, 90]
继续调整索引4（值为11）：
- 无子节点，停止
最终状态：[34, 22, 25, 12, 11, 64, 90]2.3 第三次提取
当前堆：[34, 22, 25, 12, 11, 64, 90]
堆顶元素：34（最大值）
将34与最后一个元素11交换：
[11, 22, 25, 12, 34, 64, 90]
对剩余元素[11, 22, 25, 12]重新构建最大堆：
处理索引0（值为11）：
- 左子节点：22
- 右子节点：25
比较：11 < 25，交换
[25, 22, 11, 12, 34, 64, 90]
继续调整索引2（值为11）：
- 左子节点：无
- 右子节点：无
无需调整
最终状态：[25, 22, 11, 12, 34, 64, 90]2.4 第四次提取
当前堆：[25, 22, 11, 12, 34, 64, 90]
堆顶元素：25（最大值）
将25与最后一个元素12交换：
[12, 22, 11, 25, 34, 64, 90]
对剩余元素[12, 22, 11]重新构建最大堆：
处理索引0（值为12）：
- 左子节点：22
- 右子节点：11
比较：12 < 22，交换
[22, 12, 11, 25, 34, 64, 90]
继续调整索引1（值为12）：
- 左子节点：无
- 右子节点：无
无需调整
最终状态：[22, 12, 11, 25, 34, 64, 90]2.5 第五次提取
当前堆：[22, 12, 11, 25, 34, 64, 90]
堆顶元素：22（最大值）
将22与最后一个元素11交换：
[11, 12, 22, 25, 34, 64, 90]
对剩余元素[11, 12]重新构建最大堆：
处理索引0（值为11）：
- 左子节点：12
- 右子节点：无
比较：11 < 12，交换
[12, 11, 22, 25, 34, 64, 90]2.6 第六次提取
当前堆：[12, 11, 22, 25, 34, 64, 90]
堆顶元素：12（最大值）
将12与最后一个元素11交换：
[11, 12, 22, 25, 34, 64, 90]
剩余元素只有[11]，无需重新构建堆2.7 完成排序
最终结果：[11, 12, 22, 25, 34, 64, 90]代码实现参考：冒泡排序、选择排序、插入排序、快速排序-CSDN博客
堆的数组表示推导（重要）
1.完全二叉树的特性
- 节点编号：从上到下，从左到右依次编号
- 父子关系：对于任意节点i，其子节点编号为2i+1和2i+2
- 父节点关系：对于任意节点i，其父节点编号为(i-1)/2
完全二叉树：
0
/ \
1 2
/ \ / \
3 4 5 6
数组表示：[A, B, C, D, E, F, G]
索引： [0, 1, 2, 3, 4, 5, 6]2.父子节点索引计算公式的推导
子节点公式推导：
假设：对于节点i，其子节点为2i+1和2i+2
证明过程：
- 根节点（i=0）：
- 左子节点：2×0+1=1 ✓
- 右子节点：2×0+2=2 ✓
- 第一层节点（i=1）：
- 左子节点：2×1+1=3 ✓
- 右子节点：2×1+2=4 ✓
- 第一层节点（i=2）：
- 左子节点：2×2+1=5 ✓
- 右子节点：2×2+2=6 ✓
一般情况：
- 对于节点i，其子节点在下一层
- 如果i是父节点，那么它的子节点编号应该是：2i+1和2i+2
父节点公式推导：
- 如果节点j是节点i的子节点，那么i=(j-1)/2
- 对于左子节点：j=2i+1，所以i=(j-1)/2
- 对于右子节点：j=2i+2，所以i=(j-2)/2=(j-1)/2（整数除法）
3.最后一个非叶子节点的索引推导
还是通过数学分析来证明这个公式：
观察：
- 在完全二叉树中，叶子节点都在最后两层
- 最后一个非叶子节点是最后一个有子节点的节点
- 如果数组长度为n，那么最后一个节点的索引是n-1
推导过程：
1.最后一个节点的索引：n-1
2.最后一个节点的父节点：
- 如果n-1是左子节点：父节点 = ((n-1)-1)/2 = (n-2)/2
- 如果n-1是右子节点：父节点 = ((n-1)-2)/2 = (n-3)/2
3.统一公式：
- 当n为偶数时：(n-2)/2 = n/2 - 1
- 当n为奇数时：(n-2)/2 = (n-1)/2 - 1/2 = n/2 - 1（整数除法）
举例
例子1：n=7
数组：[A, B, C, D, E, F, G]
索引：[0, 1, 2, 3, 4, 5, 6]
完全二叉树：
0
/ \
1 2
/ \ / \
3 4 5 6
最后一个节点：索引6
最后一个非叶子节点：索引2（节点C）
公式计算：(7/2)-1 = 3-1 = 2 ✓例子2：n=6
数组：[A, B, C, D, E, F]
索引：[0, 1, 2, 3, 4, 5]
完全二叉树：
0
/ \
1 2
/ \ /
3 4 5
最后一个节点：索引5
最后一个非叶子节点：索引2（节点C）
公式计算：(6/2)-1 = 3-1 = 2 ✓例子3：n=5
数组：[A, B, C, D, E]
索引：[0, 1, 2, 3, 4]
完全二叉树：
0
/ \
1 2
/ \
3 4
最后一个节点：索引4
最后一个非叶子节点：索引1（节点B）
公式计算：(5/2)-1 = 2-1 = 1 ✓