堆（heap）的概念及其实现

前言：

  在学习完树后，我进入到堆的学习，总的来说堆就是一种特殊的树，以下是我对堆的一些总结和归纳：

概念:

堆：一种有特殊用途的数据结构--用来在一组变化频繁（增删查改频率高）的数据中查找最值

堆的物理层面：表现为一组连续的数组区间

堆的逻辑层面：一颗满完全二叉树

小堆和大堆：满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆；反之，则是小堆，或者小根堆，或者最小堆。当一个堆为大堆时，它的每一棵子树都是大堆

• 小堆要求：任意一个父亲<=孩子
• 大堆要求：任意一个父亲>=孩子
• 强调：没有中堆这个概念

 堆的实现：

  头文件

初始化：

销毁：

堆的插入：

1.先判断空间是否充足，空间不够则需要扩容

2.将数据插入到最后一个位置

3.向上调整（重点）

向上调整思路图：

代码实现：

现在可以在test.c中测试一下：

完美实现!

堆的删除：

  在堆的删除中不是像以前一样删除最后一个元素，我们一般规定在堆的删除中是删除根节点，

所以堆的删除基本思路就是：

1.将根节点和最后一个元素交换

2.size--删除最后一个元素，也就是删除了之前的根节点

3.从根节点开始向下调整

向下调整基本思路：

代码实现：

放入test.c中测试一下：

完美实现！

返回堆顶元素：

返回堆内元素个数：

判空:

最后一起放入test.c中检查一哈：

完美实现！

那么堆的实现就告一段落了，快自己打开编译器实践一下把。