---------------说起堆,很难不去联想到二叉树。
目录
(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).
谢谢你的阅读,祝你好运!~



