新开的网站建设公司如何推广,手机免费制作软件下载,百度app制作网站,江苏嘉瑞通建设有限公司网站文章目录 堆排序二叉树堆堆排序的过程#xff1a;代码实现python中的heapq模块 堆排序
二叉树
关于二叉树的操作#xff0c;其实核心就是 父节点找子节点#xff0c;子节点找父节点
如果要将二叉树存储到队列中#xff0c;就需要找出 父子节点之间的规律#xff1a;
父… 文章目录 堆排序二叉树堆堆排序的过程代码实现python中的heapq模块 堆排序
二叉树
关于二叉树的操作其实核心就是 父节点找子节点子节点找父节点
如果要将二叉树存储到队列中就需要找出 父子节点之间的规律
父找子 2i1父与左 2i2父与右子找父i-1//2 堆 完全二叉树 构造堆从最后一个非叶子节点开始调整
堆排序的过程 代码实现 堆排序时间复杂度 O(N*logN)
每次调整的时候要么走左边要么走右边每次只会走一个树的高度logN
def sift(li, low, high):调整函数无论是构建堆还是移动堆都需要这个调整函数:param low: 根节点:param high: 堆最后一个元素的位置:return:1. 先把根节点拿出来2. 比较左右节点大小选择替换3. 将拿出来的根节点放到合适位置i low # i最开始指向根节点j 2 * i 1 # j开始是左孩子tmp li[low] # 把堆顶存起来while j high: # 只要j位置有数if j 1 high and li[j 1] li[j]: # 如果右孩子有并且比较大j j 1 # j指向右孩子if li[j] tmp:li[i] li[j]i j # 往下看一层j 2 * i 1else: # tmp更大把tmp放到i的位置上li[i] tmp # 把tmp放到某一级领导位置上breakelse:li[i] tmp # 把tmp放到叶子节点上def heap_sort(li):1. 构建大根堆2. 调整堆为完全二叉树3.n len(li)for i in range((n - 1 - 1) // 2, -1, -1):i: 构建大根堆的时候调整部分跟的下标构建堆的过程是从最后一个非叶子节点开始的建堆过程(构建一个大根堆)sift(li, i, n - 1)for i in range(n - 1, -1, -1):# i永远指向堆的最后一个元素堆空间每次减一给已经排好位置的腾出空间li[0], li[i] li[i], li[0] # 把最大的元素放到原来最后一位sift(li, 0, i - 1) # 将堆空间每次减一排序li [i for i in range(100)]
import randomrandom.shuffle(li)
print(li)heap_sort(li)
print(li)python中的heapq模块
python有一个内置的推排序模块在构建堆的时候构建的是小根堆
import random
import heapqli [random.randint(1, 101) for i in range(10)]
print(li)
heapq.heapify(li) # 建堆小根堆
for i in range(len(li)):tmp heapq.heappop(li) # 弹出一个最小元素若有错误与不足请指出关注DPT一起进步吧
