企业官网建设流程全解析

哪种网站,室内设计师个人简介,网站地图网页的制作,网络推广方案的参考文献堆排序的核心思想是利用堆这种特殊的完全二叉树结构进行排序#xff0c;其中大根堆要求父节点的值不小于其子节点的值#xff0c;从而保证堆顶元素为当前堆中的最大值。以下是基于序列 (55,60,40,10,80,65,15,5,75) 实现堆排序中“交换堆顶与末尾元素、调整堆”的核心循环逻辑…堆排序的核心思想是利用堆这种特殊的完全二叉树结构进行排序其中大根堆要求父节点的值不小于其子节点的值从而保证堆顶元素为当前堆中的最大值。以下是基于序列 (55,60,40,10,80,65,15,5,75) 实现堆排序中“交换堆顶与末尾元素、调整堆”的核心循环逻辑的代码片段defheapify(arr,n,i):调整以 i 为根的子树为大根堆largesti# 初始化最大值为根节点left2*i1# 左子节点right2*i2# 右子节点# 如果左子节点存在且大于根ifleftnandarr[left]arr[largest]:largestleft# 如果右子节点存在且大于当前最大值ifrightnandarr[right]arr[largest]:largestright# 如果最大值不是根节点则交换并继续调整iflargest!i:arr[i],arr[largest]arr[largest],arr[i]heapify(arr,n,largest)# 递归调整受影响的子树defheap_sort(arr):堆排序主函数nlen(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−14−13 9 // 2 - 1 4 - 1 39//2−14−13即索引 3 的元素值为 10是最后一个非叶子节点。它有两个子节点左子2*31 7→ arr[7] 5右子2*32 8→ arr[8] 75再往后索引 4 到 8 都是叶子节点无需调整。结论✅ 所以在堆排序中构建堆时应从索引n//2 - 1开始逆序遍历到 0依次对每个非叶子节点调用heapify。foriinrange(n//2-1,-1,-1):heapify(arr,n,i)这是正确且高效的建堆顺序。