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:10443/archives/635/" target="_blank" class="post_inser_a no-external-link"> <div class="inner-image bg" style="background-image: url(https://blog.beijixs.cn:10443/usr/themes/handsome/assets/img/sj/2.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:10443/usr/uploads/2020/07/2772612532.png [2]: https://blog.beijixs.cn:10443/usr/uploads/2020/07/2772612532.png [3]: https://blog.beijixs.cn:10443/usr/uploads/2020/07/3687048336.png [4]: https://blog.beijixs.cn:10443/usr/uploads/2020/07/2970155477.png Last modification：July 15th, 2020 at 03:26 pm © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
