栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

排序篇(壹) 堆排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

排序篇(壹) 堆排序

 ---------------说起堆,很难不去联想到二叉树。

目录

(1)堆的概念以及结构

①为什么未出现堆这个概念?

②堆 有什么性质?

(2)堆的实现

①向下调整法 那些事儿

那如何建大堆呢?或者如果 数组序列不符合 向下调整法的前提,又该怎样做?

②建堆:

​编辑 ③如何用堆实现排序?

​编辑

④小插曲~  为什么建堆的时间复杂度为O(n)? 那么堆排序的时间复杂度是多少呢?

(3)堆的功能

堆的增和删:

总结:


(1)堆的概念以及结构

①为什么未出现堆这个概念? 普通的二叉树是不适合用 数组来存储 的,因为可能 会存在大量的空间浪费 。而 完全二叉树更适合使用顺序结构存储 。 因此,实际上,堆其实就完全二叉树。 但注意:这里的堆,是 数据结构里的堆 。用来管理数据的。             不同于操 作系统中管理内存的堆区 !!!

②堆 有什么性质?

1.堆中某个节点的数值,总是大于或小于 ”左右子树”。

2.堆总是一棵完全二叉树。

根据性质1,也就可以把堆分为大堆、小堆>_

这是一组很平常的数组. 下图所示:

把它们按照二叉树的形式分离:

可以看见,此时每个节点的值,并不满足性质1,所以此时并不构成堆。

进行这样调整后,每个节点的值,都小于左右子树的节点。

此结构为小堆.......

我们把这个方法叫做——"向下调整法”。(之后会代码实现)

但,这个方法有个前提,必须是满足左、右子树都是堆的情况。 

(2)堆的实现

①向下调整法 那些事儿

要理解、搞懂堆排序,你不得不弄懂“向下调整法”的思想;以及代码的实现。

向下调整法:

顾名思义,从“堆顶”开始,向下调整。和两个下节点比较。建小堆就把大的数值往下调或建大堆就把小的数值往下调。

根据二叉树的性质,我们可以借助数组的下标,找到每个节点对应的位置:

我们暂时称根为父亲节点(parent),子树为孩子(child) 

而,向下调整法,从上往下,是用父亲节点找孩子节点,所以设定函数参数parent好辨识。

我们很难知道到底,左右孩子谁的值小,因此就先假定左孩子小,如果不是就++child。

一旦父节点大于孩子节点,因为建小堆,大的数要往后放,所以父亲节点和孩子节点交换 

并更新parent与child节点。

否则,也就是父节点的值,小于孩子节点,也就不用在调整了。因为前提是左右子树都是小堆。 

注:细心的朋友或许就发现了上述代码有一处不妥。

如果,当调整一层的节点只有左孩子而没得右孩子呢? 

所以我们要加上这一句,防止数组越界~ 

图示的关系,让我们理解透 向下调整的终止条件。

结果:小堆

那如何建大堆呢?或者如果 数组序列不符合 向下调整法的前提,又该怎样做?

②建堆:

从倒数第一个非叶子节点开始调整,一直调整到根节点的数。

 小堆:

 大堆在建堆的基础上,也就不用再去考虑左右子树是不是大堆----

改改 调整法中的大小于即可:

 ③如何用堆实现排序?

说起用堆排序,不同的排序方式需要不同的堆。

比如,如果要排列升序,那么就需要构建大堆!而非小堆。

④小插曲~  为什么建堆的时间复杂度为O(n)? 那么堆排序的时间复杂度是多少呢?

完全二叉树,可以在一定程度上看成满二叉树:

堆的排序和算法到这里也就告一段落啦~

(3)堆的功能

最后呢,就来写写堆的一些类似 栈、队列的功能。

堆的初始化、堆顶以及堆的有效数个数都很简单,也就不多分析。

 

堆的增和删:

 增加数据,虽然和其他线性表大同小异,但堆毕竟是堆,不能让插入的数据,打乱堆的结构。

因此如何才能让,插入的数,到达他应该去的位置?

删除数据: 堆删除元素,我们采取去堆顶

总结: ①堆特别重要的就是 向下调整法,但他的前提是,根节点的左右子树必须是堆 ②如果不是堆,那就从最后一个非叶子节点,进行调整。 ③堆增加数据,需要向上调整。 ④建堆的时间复杂度为O(n)  向下调整的时间复杂度为O(logN) 堆排序的时间复杂度为O(N*logN).

谢谢你的阅读,祝你好运!~

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/964348.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号