【初阶数据结构和算法】二叉树顺序结构---堆的定义与实现(附源码)

文章目录

• 一、堆的定义与结构
• 二、堆的实现
• • 1.堆的初始化和销毁
  • • 堆的初始化
    • 堆的销毁
  • 2.向上调整算法和入堆
  • • 向上调整算法
    • 入堆
  • 3.向下调整算法和出堆顶数据
  • • 向下调整算法
    • 出堆
  • 4.堆的有效数据个数和判空
  • • 堆的有效数据个数
    • 堆的判空
  • 5.取堆顶数据
• 三、堆的源码

一、堆的定义与结构

   本篇内容与树和二叉树的知识相关，如果还不了解什么是树，什么是二叉树，那么可以先看这篇文章了解树和二叉树的基础知识：【初阶数据结构和算法】初识树与二叉树的概念以及堆和完全二叉树之间的关系
   堆的本质是一颗完全二叉树，只是它的要求比完全二叉树更加严格，它要求每颗子树的根节点都是当前子树的最大值或最小值，当根节点是最大值时，它就是一个大根堆，当根节点是最小值时，它就是一个小根堆
   在上篇文章中我们也提到了，存储完全二叉树可以使用数组，存储非完全二叉树可以使用链表，而堆就是一种特殊的完全二叉树，所以堆的存储我们就使用数组，也就是顺序表的形式，如图：

   我们将堆这个完全二叉树从上至下，从左至右的数据存放在数组中，至于怎么保证它每颗子树的根节点都是当前子树的最大值或最小值，我们在入堆和出堆的位置细讲，而顺序表的结构我们已经很熟悉了，这里直接写出来：

typedef int HPDataType;typedef struct Heap{ HPDataType* arr;int size;int capacity;}HP;

二、堆的实现

1.堆的初始化和销毁

   堆的初始化和销毁与顺序表的初始化和销毁一致，这里我们只简单提一下

堆的初始化

   堆的初始化就是将数组置空，有效数据个数和容量大小置0，如下：

//堆的初始化void HPInit(HP* php){ assert(php);php->arr = NULL;php->size = php->capacity = 0;}

堆的销毁

   堆的销毁就是先判断数组是否为空，不为空就将它释放掉，因为数组的空间是我们向操作系统申请来的，不会主动释放，如果我们不主动释放就会造成内存泄漏，最后我们将数组置空，有效数据个数和容量大小置0，如下：

//堆的销毁void HPDestroy(HP* php){ assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;}

2.向上调整算法和入堆

   接下来就是入堆操作，也就是向堆中插入数据，但是我们要知道，一般往数组中插入数据都是向数组尾部插入，那么是不是就会出现，原本堆的每颗子树的根节点都是当前子树的最大值或最小值，但是从尾部插入数据后会打破这个平衡，如图：

   可以看到，原本的堆是一个小根堆，但是我们插入一个5之后，它就不构成小根堆了，这个时候就要用到我们的向上调整算法，当然，如果插入一个数据后还依然构成小根堆的话，我们就不做处理即可

向上调整算法

   在讲解向上调整算法时，我们就统一以小根堆为例，向上调整算法的本质就是将我们插入的数据当作孩子节点，让它和它的父节点进行比较
   那么有了孩子节点，怎么找到父节点呢？其实我们在上一篇讲过，父节点parent的下标等于(child-1)/2，找到父节点后，我们就看插入的数据是不是比它的父节点还小，如果是那么就直接进行交换，否则就不做操作，如图：

   但是我们发现交换一次后还是没有构成小根堆，所以向上调整算法要求，只要我们做了交换，那么就让child走到parent，parent再走到新的child的父节点，继续进行比较，直到child为0，此时它就没有父亲节点了，停止向上调整，如图：




   可能光说有点不理解，但是我们画图之后思路就很清晰了，接下来我们就开始按照上面的思路将代码写出来，如下：

//向上调整void AdjustUp(HPDataType* arr, int child){  //根据传来的孩子节点找到父节点int parent = (child - 1) / 2;//只要child不为0就一直循环while (child > 0){  //如果孩子比父亲小就进行交换if (arr[child] < arr[parent]){ Swap(&arr[child], &arr[parent]);//让孩子节点走到父亲节点的位置child = parent;//让父亲节点走到新的孩子节点的父节点parent = (child - 1) / 2;}