企业官网建设流程全解析

酒店网站建设描述,个人网页制作,google seo 优化招聘,购物网站开发毕业设计开题报告堆是一种特殊的完全二叉树结构#xff0c;用于高效实现优先队列。其基本性质如下#xff1a;结构性质#xff1a;堆是一棵完全二叉树#xff0c;可以用数组紧凑存储#xff0c;无空洞。 对于数组下标从 0 开始的情况#xff1a; 节点 i 的父节点下标为 (i-1)//2左孩子下标…堆是一种特殊的完全二叉树结构用于高效实现优先队列。其基本性质如下结构性质堆是一棵完全二叉树可以用数组紧凑存储无空洞。对于数组下标从 0 开始的情况节点i的父节点下标为(i-1)//2左孩子下标为2*i1右孩子为2*i2堆序性质大根堆最大堆任意节点的值 ≥ 其左右子节点的值根节点为最大值。小根堆最小堆任意节点的值 ≤ 其左右子节点的值根节点为最小值。建堆过程自底向上调整从最后一个非叶子节点开始即第⌊n/2⌋ - 1个元素0起始索引向前依次调用HeapAdjust函数进行向下调整直到根节点。时间复杂度为 O(n)优于逐个插入的 O(n log n)。HeapAdjust调整函数以大根堆为例defheap_adjust(data,s,m):# 在 data[s..m] 中仅 data[s] 可能不满足堆性质其余已满足tempdata[s]child2*s1# 左孩子whilechildm:# 找出较大的子节点ifchildmanddata[child]data[child1]:child1# 如果根不小于子节点则已合适iftempdata[child]:break# 否则将较大子节点上移data[s]data[child]schild child2*s1data[s]temp# 插入原 data[s] 到正确位置HeapSort堆排序算法defheap_sort(data):nlen(data)# 构建大根堆从最后一个非叶节点开始调整foriinrange(n//2-1,-1,-1):heap_adjust(data,i,n-1)# 逐个提取堆顶并重建堆foriinrange(n-1,0,-1):data[0],data[i]data[i],data[0]# 堆顶与末尾交换heap_adjust(data,0,i-1)# 重新调整剩余元素成堆性能分析时间复杂度O(n log n) —— 建堆 O(n)每次调整 O(log n)共 n−1 次。空间复杂度O(1)原地排序。稳定性不稳定相同元素可能因父子交换而改变相对顺序。适用场景数据量大且对最坏情况有要求相比快排更稳定Top-K 问题如找最大前 K 个数实时系统中需要可预测性能的排序任务。将一个数组原地构建成小根堆的过程与构建大根堆类似核心思想是利用完全二叉树的结构特性和自底向上的调整策略。只需在调整函数中将比较方向反转父节点 ≤ 子节点即可实现小根堆。步骤说明存储方式使用数组表示完全二叉树索引从 0 开始。节点i的左孩子为2*i1右孩子为2*i2父节点为(i-1)//2关键点最后一个非叶子节点的下标是⌊n/2⌋ - 1因为叶子节点没有子节点。调整顺序从该节点开始向前逐个调用min_heap_adjust函数进行“向下筛选”。Python 实现代码defmin_heap_adjust(data,s,m): 调整 data[s] 使得子树 data[s..m] 满足小根堆性质 前提data[s] 的左右子树已经是小根堆 tempdata[s]child2*s1# 左孩子whilechildm:# 选择较小的子节点ifchildmanddata[child]data[child1]:child1# 如果当前值已经不大于子节点则位置合适iftempdata[child]:break# 否则将较小的子节点上移data[s]data[child]schild child2*s1data[s]temp# 将原值放入正确位置defbuild_min_heap(data): 将数组 data 原地构建成小根堆 nlen(data)# 从最后一个非叶子节点开始向前调整foriinrange(n//2-1,-1,-1):min_heap_adjust(data,i,n-1)# 示例使用arr[4,10,3,5,1]build_min_heap(arr)print(小根堆:,arr)# 输出如: [1, 4, 3, 5, 10]特点分析时间复杂度O(n)虽然单次调整为 O(log n)但由于树的层次分布特性整体建堆为线性。空间复杂度O(1)原地操作。稳定性堆排序本身不稳定但建堆过程不影响稳定性讨论排序时才体现。通过上述方法可以高效地将任意数组原地转换为一个小根堆适用于最小优先队列、Top-K 最小元素等问题。