3. 堆化的详细过程 堆化是堆排序中非常重要的一步， 5， i ) : # 初始化最大值为当前节点索引 largest i # 计算左子节点的索引 left 2 * i 1 # 计算右子节点的索引 right 2 * i 2 # 如果左子节点存在索引小于堆大小且左子节点的值大于当前最大值 if left heap_size and arr [ left ] arr [ largest ] : # 更新最大值索引为左子节点 largest left # 如果右子节点存在索引小于堆大小且右子节点的值大于当前最大值 if right heap_size and arr [ right ] arr [ largest ] : # 更新最大值索引为右子节点 largest right # 如果最大值不是当前节点说明需要调整 if largest ! i : # 交换当前节点和最大值节点 arr [ i ] ， 1.3 接下来堆化索引 0 索引 0 的元素是 4 左子节点索引2 * 0 1 1对应元素 10 右子节点索引2 * 0 2 2对应元素 3 比较 当前节点 4与左子节点 10 和右子节点 3 比较最大的值为 10索引 1， 1]根节点为最大值 5，此时堆顶的元素是当前数组中的最大元素， 5， 13 ， 10] 交换索引 0 与索引 3 交换后数组变为 [1， 2.3 第三次交换 交换堆顶与堆的最后一个元素 当前数组[4， 5， arr [ largest ] arr [ largest ] ， 5， 10， 4， 4， 1， arr [ 0 ] # 对剩余未排序部分重新堆化保持大顶堆性质 heapify ( arr ， array ) # 输出排序后的数组 总结 我们可以总结堆排序的关键步骤 构建大顶堆 从最后一个非叶节点开始依次对节点进行堆化构建一个大顶堆， 1] 我们目标是使用大顶堆来排序使得排序后得到升序排列的数组，通过这个过程我们可以确保堆顶根节点的元素是当前堆中最大的， 堆化过程 对索引 0值 3堆化 左子节点索引1值为 1 3 大于 1无需交换， 3， 3， 4，然后缩小堆的范围并对新的堆顶元素执行堆化操作保证堆顶元素仍然是最大值， 1.5 构建大顶堆结果 经过上述堆化过程整个数组已经构建成大顶堆数组状态为 [10。
10] 继续堆化索引 1值为 1 左子节点索引3值为 4 右子节点索引4不在堆的范围内堆大小为 4 比较最大值为 4索引 3，我们从该节点开始依次进行堆化直到堆化到根节点， arr [ i ] arr [ i ] ， 排序过程 每次将堆顶元素与最后一个元素交换后都需要对剩余的部分执行堆化， 5， 如果当前节点的值已经大于或等于其左右子节点的值则堆化过程结束， 索引 0 的元素1 左子节点索引1值为 5 右子节点索引2值为 3 比较最大值为 5索引 1， 3， 6 ，堆顶根节点元素是整个堆中 最大 的， 1]堆大小为 2， 3， 5，排序时首先构建大顶堆然后将堆顶元素与数组最后一个元素交换再对剩余的部分重新构建大顶堆如此循环直到整个序列有序， arr [ i ] # 递归调整交换后的子树以保持堆的性质 heapify ( arr 。
4，堆顶根节点元素是整个堆中 最小 的， 3， 堆化后子树保持[10， heap_size ， 5 ， 对新的堆顶元素执行堆化恢复堆的性质。
- 1 ) : # 从最后一个非叶子节点开始向上调整堆 heapify ( arr ， 1。
小顶堆Min Heap 每个结点的值都 小于或等于 其左右子结点的值， 4， 3， 3， 四、 Python 实现示例 以下是一个简单的 Python 实现示例帮助更好地理解具体实现步骤 # 堆调整函数 def heapify ( arr ， 4，。
10] 交换索引 0 与索引 1 交换后数组变为 [1， 堆化过程 从索引 0 开始堆化，我们将堆顶元素与数组的最后一个元素交换位置将最大元素“移出”堆外。
1] 交换索引 0 与索引 4最后一个元素 交换后数组变为 [1， 1， 交换将 1 与 5 交换数组变为 [5， array ) # 输出原始数组 heap_sort ( array ) # 调用堆排序函数对数组进行排序 print ( 排序后的数组: ， 排序后堆调整完成堆为[5， 5，每次堆化的时间复杂度为 O(log n)一共需要执行 n - 1 次交换因此排序过程的时间复杂度为 O(n log n)， 3， 1。
4， 假设数组的长度是 n那么最后一个非叶子节点的索引为 (n // 2) - 1， largest ) # 堆排序函数 def heap_sort ( arr ) : n len ( arr ) # 获取数组长度 # 构建大顶堆 for i in range ( n // 2 - 1 ，大顶堆的特点是每个父节点的值都大于或等于其左右子节点的值， 2.4 第四次交换 交换堆顶与堆的最后一个元素 当前数组[3， 3， 交换将 1 与 4 交换数组变为 [4， 1] 索引 3值 4是叶子节点无需继续堆化， 交换后数组变为[10， 1， i ) # 排序过程 for i in range ( n - 1 ， 2.1 第一次交换 交换堆顶与最后一个元素 当前数组[10， 堆排序通常使用大顶堆来实现升序排序， 最终排序结果 经过上述所有交换和堆化数组最终变为 [1， i ， 5， 交换后需要继续对交换后的子树进行堆化操作确保堆的性质， 11 ， 4， 10] 对索引 1值 1 左子节点索引3不在堆范围内堆大小为 3 堆化结束， 3， 10] 说明此时最大值 10 固定在最后位置不参与后续堆化，所以堆排序的空间复杂度为 O(1) ， 1] 根节点 10 为最大值 对应的二叉树结构为10/ \5 3/ \4 1 第二步排序过程 排序过程的目标是不断把堆顶最大值交换到数组末尾然后对剩余部分重新堆化， 1， 4， n ， - 1 ) : # 将堆顶最大值与当前未排序部分的最后一个元素交换 arr [ 0 ] 。
3]。
1]，堆化的过程可以分为以下几个步骤 比较当前节点和其左右子节点的值找到三者中最大的一个。
排序过程 将堆顶最大值与数组末尾交换把最大值固定到正确位置 缩小堆的有效范围对新的堆顶进行堆化确保剩余部分仍然是大顶堆 重复以上过程直到排序完成，重复这个过程直到堆的大小缩小到 1， 3， 5， 因此堆排序的总时间复杂度为 O(n log n) 这是一个较为稳定的时间复杂度， 排序后堆调整完成堆为[3。
5， 4. 堆排序的完整步骤总结 构建大顶堆 从最后一个非叶子节点开始依次对每个节点进行堆化构建大顶堆， 4， 5， 10] 说明当前最大值 5 固定在正确位置。
5， 将堆的大小减 1即排好序的部分不再参与堆化。
10] 此时只剩下一个元素不需要再堆化， 4， 0 ) # 示例用法 if __name__ __main__ : array [ 12 ， 4， 5. 堆排序的时间复杂度 构建堆 需要进行 n / 2 次堆化每次堆化的时间复杂度为 O(log n)所以构建大顶堆的时间复杂度为 O(n)， 6. 堆排序的空间复杂度 堆排序是原地排序算法除了原始数组外不需要额外的存储空间， 3。
一、 堆的基本概念 二、 堆排序的主要步骤 1. 构建大顶堆Max-Heap 2. 排序过程 3. 堆化的详细过程 4. 堆排序的完整步骤总结 5. 堆排序的时间复杂度 6. 堆排序的空间复杂度 三、 举例讲解 示例数组 第一步构建大顶堆 1.1 找到最后一个非叶子节点 1.2 从索引 1 开始堆化 1.3 接下来堆化索引 0 1.4 检验并判断是否需要重新堆化 1.5 构建大顶堆结果 第二步排序过程 2.1 第一次交换 堆化过程 2.2 第二次交换 堆化过程 2.3 第三次交换 堆化过程 2.4 第四次交换 最终排序结果 四、 Python 实现示例 总结 一、 堆的基本概念 堆是一种完全二叉树可以分为两种类型 大顶堆Max Heap 每个结点的值都 大于或等于 其左右子结点的值， 5， 10] 这就是堆排序完成后的结果数组按升序排列， 3。
第一步构建大顶堆1.1 找到最后一个非叶子节点 对于长度 n5 的数组最后一个非叶子节点索引为 floor(n/2) - 1 floor(5/2) - 1 2 - 1 1 所以从索引 1 开始往前包括索引 0依次堆化， 3]堆大小为 3， 三、 举例讲解示例数组 假设初始数组为 [4， 1]索引 1 及其子节点不变， 1， 1.2 从索引 1 开始堆化 索引 1 的元素是 10 左子节点索引2 * 1 1 3对应元素 5 右子节点索引2 * 1 2 4对应元素 1 比较 10 与 5、1 比较10 已经大于其两个子节点无需交换， 10] 交换索引 0 与索引 2 交换后数组变为 [3。
10] 固定最大值 4 在位置索引 2， 排序过程 将堆顶元素与数组的最后一个元素交换减小堆的大小，它的目标是从某个节点开始调整树的结构使其满足堆的性质即父节点的值大于或等于子节点的值， 交换将 4 与 10 交换数组变为[10， 为什么从最后一个非叶子节点开始 因为叶子节点本身就是堆只有非叶子节点可能不满足堆的性质因此从最后一个非叶子节点开始堆化可以确保堆化时每个子树都已经是有效的堆， 0 ， 对于某个父节点比较其左右子节点选出较大的子节点将父节点与较大的子节点交换位置递归继续向下堆化直到堆的性质满足， 3， 排序后堆调整完成堆为[4， 堆化过程 对索引 0值 1堆化 左子节点索引1值为 4 右子节点索引2值为 3 最大值为 4索引 1， 1， 5。
3。
5， 4， 3， 堆化结束， 具体步骤 从最后一个非叶子节点开始对每个节点进行“堆化”heapify操作直到根节点， 10] 索引 3 为叶子节点堆化结束， 如果当前节点的值小于其子节点则将当前节点与最大子节点交换， 1] 1.4 检验并判断是否需要重新堆化 交换后以原索引 1 的位置现在值为 4的子树需要重新堆化 对于 索引 1 当前值 4 左子节点索引2 * 1 1 3对应元素 5 右子节点索引2 * 1 2 4对应元素 1 比较 在 4、5、1 中最大值是 5索引 3所以交换 4 与 5。
2. 排序过程 构建好大顶堆后我们进入排序阶段， 2.2 第二次交换 交换堆顶与堆的最后一个元素 当前数组[5， 对堆顶元素执行堆化操作保证剩下的部分仍然是大顶堆， 4， 重复步骤 1 至步骤 3直到堆的大小为 1。
。
交换将 1 与 4 交换数组变为 [5， 对剩余堆索引 0 到 1重新堆化 子数组为[3， 重复上述过程直到堆的大小为 1， 7 ] # 定义一个待排序数组 print ( 原始数组: 。
堆化的作用是确保每个子树的结构满足堆的性质， 具体步骤 将堆顶元素最大元素与数组的最后一个元素交换， 对剩余堆索引 0 到 3重新堆化 子数组为[1， 4， heap_size ， - 1 。
二、 堆排序的主要步骤1. 构建大顶堆Max-Heap 堆排序首先需要将输入的无序数组调整为一个大顶堆Max-Heap， 4]堆的大小为 4。
对剩余堆索引 0 到 2重新堆化 子数组为[1。
堆化Heapify 堆化的目标是确保一个父节点大于其子节点。