Loading... ##前言 堆排序需要将一颗完全二叉树构建成一个大顶堆或者小顶堆,然后将堆顶和最后的数字交交换 **什么是大顶堆?** ![大顶堆][1] <div class="tip inlineBlock info"> 堆顶一定是最大值,父结点一定是三个值之间最大的值。小顶堆与其相反。 其中最大值为堆顶,第二层一定有一个次大值 </div> **二叉树的性质四** - 具有n个节点的 完全二叉树 的深度为int(log_2n)+1 或者 math.ceil(log_2(n+1)) # log_2 对数的意思 - int(math.log(n)) + 1 **二叉树的性质五** 如果有一颗n个结点的完全二叉树(深度为性质4).结点按照层序编号(i),如下: 1 2 3 4 5 6 7 8 9 10 - 如果i=1,则结点i是二叉树的根,无双亲; - 如果i>1,则其双亲是`int(i/2)`,向下取整。就是子节点的编号除以2得到的就是父结点的编号。 - 父结点如果是i,那么左孩子结点就是`2i`,右孩子结点就是`2i+1` - 如果`2i>n`,则结点i无左孩子,即结点i为叶子结点;否则其左孩子结点存在编号为`2i` - `n>2i` 说明存在右孩子, 且标号为: `2i+1` - 如果`2i+1>n`,则结点i`无`右孩子,注意这里并不能说明结点i没有左孩子;否者右孩子结点存在编号为`2i+1` - 完全二叉树父亲结点一共有 n//2 个(包含根结点) ## 打印二叉树 <div class="preview"> <div class="post-inser post box-shadow-wrap-normal"> <a href="https://blog.beijixs.cn/archives/635/" target="_blank" class="post_inser_a no-external-link no-underline-link"> <div class="inner-image bg" style="background-image: url(https://blog.beijixs.cn/usr/themes/handsome/assets/img/sj/1.jpg);background-size: cover;"></div> <div class="inner-content" > <p class="inser-title">二叉树打印</p> <div class="inster-summary text-muted"> 前言打印二叉树是分析堆排序的最佳方式假设有这样的棵树 30 20 ... </div> </div> </a> <!-- .inner-content #####--> </div> <!-- .post-inser ####--> </div> ## 构建大顶堆 20 40 50 ###构建单个二叉树 如上面的大顶堆,我们先判断改大顶堆是否有左孩子,然后判断右孩子 如果 有左孩子,我们假设左孩子是最大的那个树 然后判断是否有右孩子,如果有左孩子和右孩子比较,如果右孩子大于左孩子,保存右孩子为最大值 最后和父结点进行比较,如果大于父结点就交换位置,否则不变 **代码实现** def max_heap(i, n, array): """ 调整数据为大顶堆 :param i: 根节点的标号 :param n: 结点个数 :param array: 带构建的数据 :return: list 构建好的大顶堆 """ while 2 * i <= n: # 性质五:如果2i>n,则结点i无左孩子 # 这里表示有左孩子就进入循环 l_index = 2 * i # 左孩子编号 2i max_index = l_index # 假设最大的就是左孩子,这里保存索引 if 2 * i + 1 <= n and array[l_index] < array[2 * i + 1]: # 如果存在右孩子且右孩子大于左孩子,最大值索引为右孩子 max_index = 2 * i + 1 if array[max_index] > array[i]: # 最大值和根结点比较,如果最大值真的大于根节点,则交换位置 array[max_index], array[i] = array[i], array[max_index] i = max_index # 修正i,继续向下调整直到不存在孩子结点 else: # 没有孩子结点就退出循环 break return array ###全面调整二叉树为大顶堆 上面的算法从堆顶构建的话,不能达到我们的目的,但是从最后一个父结点开始就可以达到我们的目的 **代码实现** def all_heap(total, array): """ 调整整个数据为大顶堆 :param total: 结点个数 :param array: 结点列表 :return: list """ for i in range(total//2, 0, -1): # 父亲结点个数: 结点数 // 2 max_heap(i, total, array) # 因为这里全是引用类型,没有拷贝数据。节省了内存空间 # 从最后一个父结点开始调整 return array ###升序排序 ![未排序之前][2] ![第一次排序][3] 将堆顶和最后一个交换,然后重新构建大顶堆 ![重新构建大顶堆][4] 然后根系结点和最后一个结点进行交换 <div class="tip inlineBlock error"> 注意这里最后一个不是`90`,而是`20`, `90`已经不再参与大顶堆构建 </div> 依次内推 **代码实现** origin = [0, 30, 20, 80, 40, 50, 10, 60, 70, 90] origin = all_heap(len(origin) - 1, origin) # 构建大顶堆, 其实没有执行任何拷贝,直接调用函数就可以实现对origin的更改 def sort(total, array): """ 排序 :param total: 结点个数 :param array: 结点列表 :return: list """ while total > 1: array[total], array[1] = array[1], array[total] total -= 1 max_heap(1, total, array) # 重构大顶堆,因为不要最后一个结点参与,所以total - 1 if total == 2 and array[total] >= array[total - 1]: # 如果 标号为2的结点 大于或等于根节点就不做调整了 break return array 到此,排序完成 <div class="tip inlineBlock error"> 始终注意`list`类型,如果不进行拷贝的话,不管怎么引用,他们都是表示的同一段内存空间,修改任何一个引用标识符相当于修改其他标识符的数据,如a = [1, 2], b = a, a.append(3), print(b) = > [1,2,3] </div> [1]: https://blog.beijixs.cn/usr/uploads/2020/07/2772612532.png [2]: https://blog.beijixs.cn/usr/uploads/2020/07/2772612532.png [3]: https://blog.beijixs.cn/usr/uploads/2020/07/3687048336.png [4]: https://blog.beijixs.cn/usr/uploads/2020/07/2970155477.png 最后修改:2020 年 07 月 15 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用,请随意赞赏