读书笔记-《数据结构与算法》-摘要7[堆排序]

发布时间：2024年01月16日

堆排序通常基于二叉堆 实现，以大根堆为例，堆排序的实现过程分为两个子过程。第一步为取出大根堆的根节点(当前堆的最大值), 由于取走了一个节点，故需要对余下的元素重新建堆。重新建堆后继续取根节点，循环直至取完所有节点，此时数组已经有序。基本思想就是这样，不过实现上还是有些小技巧的。

堆的操作

以大根堆为例，堆的常用操作如下。

  1. 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  2. 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
  3. 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

其中步骤1是给步骤2和3用的。

在这里插入图片描述

—PS：

1、初始数据

在这里插入图片描述

2、依据父节点大于等于所有子节点，创建大根堆完成后为

在这里插入图片描述

3、然后按照前序(pre-order)：先根后左再右，将值取出

在这里插入图片描述

4、这时候数组的第一位就是最大值，与最末尾交换后，最大值就到了末尾，定死后去除节点

在这里插入图片描述

5、然后重复2->3->4

这次看这个算法是有吃力的，先知道个概念吧。看不明白的时候就去查些资料，会推荐些大佬的文章：

（八）Java算法：堆排序（详细图解）

文章来源:https://blog.csdn.net/JustDI0209/article/details/135632917
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章