在学习完树后,我进入到堆的学习,总的来说堆就是一种特殊的树,以下是我对堆的一些总结和归纳:
堆:一种有特殊用途的数据结构--用来在一组变化频繁(增删查改频率高)的数据中查找最值
堆的物理层面:表现为一组连续的数组区间
堆的逻辑层面:一颗满完全二叉树
小堆和大堆:满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆;反之,则是小堆,或者小根堆,或者最小堆。当一个堆为大堆时,它的每一棵子树都是大堆
头文件
1.先判断空间是否充足,空间不够则需要扩容
2.将数据插入到最后一个位置
3.向上调整(重点)
向上调整思路图:
代码实现:
现在可以在test.c中测试一下:
完美实现!
在堆的删除中不是像以前一样删除最后一个元素,我们一般规定在堆的删除中是删除根节点,
所以堆的删除基本思路就是:
1.将根节点和最后一个元素交换
2.size--删除最后一个元素,也就是删除了之前的根节点
3.从根节点开始向下调整
向下调整基本思路:
代码实现:
放入test.c中测试一下:
完美实现!
最后一起放入test.c中检查一哈:
完美实现!
那么堆的实现就告一段落了,快自己打开编译器实践一下把。