<= end):if (i < end):#如果结点i存在左右节点(都有)避免后续访问越界#判断到底是左孩子大还是右孩子大bigger_child_index = i#不是必须的,但是含义更加清晰if (l[i] < l[i + 1]):#如果是右孩子大,那么将i更新为i+1;否则保持i不变(默认左孩子大)bigger_child_index = i + 1i += 1#到此处，我们已经可以保证,此时的i指向的是是结点k的较大的孩子(下标)# 现在再判断这个大孩子和他们的根结点bak_k到底谁比较大if (bak_k >= l[i]):#发现根结点k不比两个孩子小,不需进一步调整,结束#这里我们用bak_k这一备份值,是因为后续我们要更新k,所以用bak_k才是正确的breakelse:#孩子结点根结点大,需要调整l[k] = l[i]#将l[i]覆盖掉l[k]# 更新k=ik = i#令k接替/指向较大孩子的位置,以便执行下一轮比较# 另外,我们手动模拟的时候可能习惯交换i和k#在代码里面也可以交换,但是本实现中没有必要,# 因为我们有l[k]的备份bak_k,因此不需要可以保存l[k]的值#可以到最后确定下来被筛选的结点要沉到哪个具体位置,在执行赋值即可#继续判断下一轮,看bak_k中的值要放在哪里i *= 2#放在else内部应该也可以(因为执行的效果是要么都执行,要么都不执行)#循环结束,bak_k的元素可以被赋值给l[k],完成调整(最终位置)l[k] = bak_kreturn l

文章插图
建堆操作/堆的插入操作(自底向上)
构造堆过程示一个自底向上的过程
我们不妨称从乱序序列开始构造堆的过程称为大调整或者假设,一个有,最大值为R,现在要加入一个结点,值很大(比如Z),Z>R如果从上往下调整,无从调起而从下往上,我们可以逐步的将Z结点往上调整到根结点
事实上,堆的调整函数可以用来构建堆(通过正确的方式调用)
以大根堆为例,假设此时大根堆有结点n个
构造堆算法堆排序算法()
def heapSort(l):print("build heap:")buildHeap(l)print(l)len_l = len(l)for i in range(len_l-1, 1, -1):print("i=%d,l[i]=%d,l[1]=%d" % (i, l[i],l[1]))#l[1]表示maxHeapTop堆顶元素(最大元素)l[i], l[1] = l[1], l[i]# print("after swap:",l)heapify(l,1,len_l=i-1)# print("after heapify maintained",i,l)print("")# print_layers2(l)return l
调用/测试上述函数
# 测试函数功能def test_print_layers(l):print(print_layers(l))def test_reserve_head_with(l):print(reserve_head_with(l))def test_heapify(l):res_heapify=heapify(l1,k=1,len_l=6)print("beautfy the result(remove the meaningless header -1 OR None):",res_heapify[1:])def test_buildHeap(l):print(buildHeap(l)[1:])def test_heapSort(l):reserve_head_with(l)print("res:",heapSort(l)[1:])if __name__ == "__main__":# main()l = [ 53, 17, 78, 9, 45, 65, 87, 32]l1 = [-1, 53, 45, 65, 32, 17, 9, 78, 87]test_heapSort(l)
堆排序性能其他操作的性能建堆稳定性代码参考 选择排序法_实数排序: (升序版） 结构梳理版
/* 选择排序法_实数排序: (升序版）有助于增强理解的特征:最大比较区间的次数为n-1次 ;最小长度比较区间比较的次数为1次.*/#include #include "d:/repos/cpp/ConsoleApps/c_codes/libs/common_funcs.c"// 找出min_loc 到j位置范围内最小?的数组索引(采用这种方案的话,每趟排序最多也只需要执行一次交换操作)int update_min_loc(float *a, int *min_loc_addr, int j){int min_loc = *min_loc_addr;if (a[min_loc] > a[j]){*min_loc_addr = j;}return *min_loc_addr;}// 在需要的时候交换start_loc和j两个位置上的元素,确保start_loc上的元素是较小的一方!int set_minor_elem(float *a, int start_loc, int j){int min_loc = start_loc;if (a[min_loc] > a[j]){swap_float_pointer(a + j, a + min_loc);}return min_loc;}// 确保位置i上的元素在[i~n]范围内是最小的void set_next_most(float *a, int n, int i){int min_loc = i;/* 找到最小元素所在位置,这里比较边界是将左边界收缩,而右边界不变. *//*指出比较范围和比较对象比较范围:起始元素向后收缩;最终元素保持不变*//*每一趟:外重循环从LHS∈[0,n-2]中选定一个LHS,内重循环控制该趟排序的一系列比较中,使RHS∈[LHS+1,n-1]全部依次与该趟指定的这个LHS作比较 */for (int j = i + 1; j

• 上一页
• 1
• 2
• 3
• 下一页

• 个性化购买力分析及在搜索排序上应用
• mysql字符串排序规则_MySQL字符集和排序规则
• 交换链接
• 二层、三层交换机是什么？有什么区别？
• 仿Android联系人SideBar排序，根据拼音A-Z字母快速导航联系人姓名
• 对链表进行插入排序
• 监控交换机选择：千兆 百兆 核心 PoE 光纤交换机选型指南
• 程序员必须掌握这几种排序算法的最佳实践，包会！ 含GIF图 世界十大算法
• 乐器难度排行榜,乐器难度，价钱排序
• 锐捷RSR系列路由器_接入路由器交换模块配置_IP+MAC绑定