企业官网建设流程全解析

堆排序的核心思想是利用堆这种特殊的完全二叉树结构进行排序，其中大根堆要求父节点的值不小于其子节点的值，从而保证堆顶元素为当前堆中的最大值。以下是基于序列 (55,60,40,10,80,65,15,5,75) 实现堆排序中“交换堆顶与末尾元素、调整堆”的核心循环逻辑的代码片段：

defheapify(arr,n,i):"""调整以 i 为根的子树为大根堆"""largest=i# 初始化最大值为根节点left=2*i+1# 左子节点right=2*i+2# 右子节点# 如果左子节点存在且大于根ifleft<nandarr[left]>arr[largest]:largest=left# 如果右子节点存在且大于当前最大值ifright<nandarr[right]>arr[largest]:largest=right# 如果最大值不是根节点，则交换并继续调整iflargest!=i:arr[i],arr[largest]=arr[largest],arr[i]heapify(arr,n,largest)# 递归调整受影响的子树defheap_sort(arr):"""堆排序主函数"""n=len(arr)# 构建大根堆（从最后一个非叶子节点开始向上调整）foriinrange(n//2-1,-1,-1):heapify(arr,n,i)# 逐个提取堆顶元素（最大值）放到数组末尾foriinrange(n-1,0,-1):arr[0],arr[i]=arr[i],arr[0]# 交换堆顶与末尾heapify(arr,i,0)# 对剩余元素重新调整为大根堆# 示例使用data=[55,60,40,10,80,65,15,5,75]print("原始序列:",data)heap_sort(data)print("排序后序列:",data)

输出结果：

原始序列: [55, 60, 40, 10, 80, 65, 15, 5, 75] 排序后序列: [5, 10, 15, 40, 55, 60, 65, 75, 80]

算法说明：

• 构建堆：从最后一个非叶子节点n//2 - 1开始，逆序向前对每个节点调用heapify，确保整个数组满足大根堆性质。
• 排序过程：将堆顶（最大值）与末尾元素交换，然后对前i个元素再次调用heapify恢复堆结构，重复此过程直到全部有序。
• 时间复杂度：建堆 O(n)，每次调整 O(logn)，共 n-1 次调整 → 总体O(n log n)。
• 空间复杂度：仅使用常数额外空间 →O(1)。
• 稳定性：由于父子节点间跳跃式交换，相同元素相对位置可能改变 →不稳定排序。
• 在堆排序中，堆是一棵完全二叉树。对于一个长度为n的数组，其对应的完全二叉树的最后一个非叶子节点是最后一个节点的父节点。

由于完全二叉树的性质：

• 数组下标从 0 开始；
• 对于任意节点索引i，其左子节点为2*i + 1，右子节点为2*i + 2；
• 反之，任意节点i的父节点索引为(i - 1) // 2。

最后一个节点的索引是n - 1，因此它的父节点就是最后一个非叶子节点：

last_non_leaf_index=(n-1-1)//2=(n-2)//2

但更简单且常用的方式是从最后一个有子节点的节点推导：
我们知道，如果某个节点i满足2*i + 1 < n，则它是非叶子节点。要找最大的这样的i。

实际上，最后一个非叶子节点的索引为：

last_non_leaf=⌊n2⌋−1 \text{last\_non\_leaf} = \left\lfloor \frac{n}{2} \right\rfloor - 1last_non_leaf=⌊2n​⌋−1

示例验证：

数组长度n = 9（如序列 [55,60,…,75]）
则最后一个非叶子节点索引为：
9//2−1=4−1=3 9 // 2 - 1 = 4 - 1 = 39//2−1=4−1=3

即索引 3 的元素（值为 10）是最后一个非叶子节点。它有两个子节点：

• 左子：2*3+1 = 7→ arr[7] = 5
• 右子：2*3+2 = 8→ arr[8] = 75

再往后，索引 4 到 8 都是叶子节点（无需调整）。

结论：

✅ 所以，在堆排序中，构建堆时应从索引n//2 - 1开始，逆序遍历到 0，依次对每个非叶子节点调用heapify。

foriinrange(n//2-1,-1,-1):heapify(arr,n,i)

这是正确且高效的建堆顺序。