【数据结构】实现堆

大家好，���是苏貝，本篇博客带大家了解堆，如果你觉得我写的还不错的话，可以给我一个赞吗，感谢❤️

目录

• 一. 堆的概念及结构
• 二. 堆的实现
• • 堆的结构体
  • 初始化
  • 销毁
  • 插入数据
  • 删除数据（默认删除堆顶即根节点）
  • 显示堆顶（即根节点）的值
  • 是否为空
  • 堆的大小
  • 三. 模块化代码实现
  • • Heap.h
    • Heap.c
    • Test.c
    • 结果演示

      一. 堆的概念及结构

      如果有一个关键码的集合K，把它的所有元素按 完全二叉树 的顺序存储方式存储在一个一维数组中，并满足：任意一个双亲结点的值=孩子节点的值），则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

      普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

      堆的性质：

      1. 堆中某个节点的值总是不大于（大堆）或不小于（小堆）其双亲节点的值；
      2. 堆总是一棵完全二叉树。

      ---

      二. 堆的实现

      上面我们说过，现实中我们通常使用顺序结构的数组来存储堆，现在让我们来实现一下小堆

      1

      堆的结构体

      我们用数组来存储堆，而且一般都使用动态数组

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

      2

      初始化

      因为函数的实参是HP类型变量的地址，不可能为空，所以对它断言，下面的接口同理。

      void HPInit(HP* php){assert(php);php->a = NULL;php->capacity = 0;php->size = 0;}

      3

      销毁

      因为数组a是动态开辟的数组，所以要在程序结束前将它释放

      void HPDestroy(HP* php){assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;}

      4

      插入数据

      在插入数据之前，我们要判断是否需要增容，增容的条件是size==capacity。判断完成后，在堆的最后面（即数组的最后面）插入数据。数据插入完成后，我们还要保证这是一个小堆，所以要对比这个数据和它的双亲结点的值：如果它的值要大于双亲结点的值，那位置就不要动；如果它的值要小于双亲结点的值，为了让这个堆还是小堆，我们要将它和双亲结点互换位置，直到它的值要大于双亲结点的值或者它已经是根节点

      void HPPush(HP* php, HPDataType x){assert(php);//是否需要增容if (php->capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");//exit(-1);return;}php->a = tmp;php->capacity = newcapacity;}//插入php->a[php->size] = x;php->size++;    //插入之后，如果堆的性质遭到破环，交换与双亲结点的位置AdjustUp(php->a, php->size - 1);}

      下面是交换与双亲结点的位置的代码

      void swap(HPDataType* a, HPDataType* b){HPDataType tmp = *a;*a = *b;*b = tmp;}void AdjustUp(HPDataType* a, int child){int parent = (child - 1) / 2;while (child > 0){if (a[child]  
      5
       
      删除数据（默认删除堆顶即根节点）
       
      删除必须保证堆中有元素，所以对堆的大小断言，下面的显示根节点同理。
      注意：AdjustDown函数中的第一个if语句是想要找到左右孩子节点中较小的一个，但不一定有右孩子节点，所以要保证child + 1  
        
      void AdjustDown(HPDataType* a, int size, int parent){int child = parent * 2 + 1;while (child  a[child]){swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//删除（默认删除的是堆顶，即根节点）void HPPop(HP* php){assert(php);assert(php->size > 0);swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);}
       
      6
       
      显示堆顶（即根节点）的值
       
      HPDataType HPTop(HP* php){assert(php);assert(php->size > 0);return php->a[0];}
       
      7
       
      是否为空
       
      bool HPEmpty(HP* php){assert(php);return php->size == 0;}
       
      8
       
      堆的大小
       
      int HPSize(HP* php){assert(php);return php->size;}
       
      三. 模块化代码实现
       
      Heap.h
       
      #include#include#include#includetypedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;}HP;//初始化void HPInit(HP* php);//销毁void HPDestroy(HP* php);//插入void HPPush(HP* php, HPDataType x);//删除（默认删除的是堆顶，即根节点）void HPPop(HP* php);//显示堆顶元素HPDataType HPTop(HP* php);//是否为空bool HPEmpty(HP* php);//堆的大小int HPSize(HP* php);
       
      Heap.c
       
      #include"Heap.h"//初始化void HPInit(HP* php){assert(php);php->a = NULL;php->capacity = 0;php->size = 0;}//销毁void HPDestroy(HP* php){assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;}void swap(HPDataType* a, HPDataType* b){HPDataType tmp = *a;*a = *b;*b = tmp;}void AdjustUp(HPDataType* a, int child){int parent = (child - 1) / 2;while (child > 0){if (a[child] capacity == php->size){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");//exit(-1);return;}php->a = tmp;php->capacity = newcapacity;}//插入php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);}void AdjustDown(HPDataType* a, int size){int parent = 0;int child = parent * 2 + 1;while (child  a[child]){swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//删除（默认删除的是堆顶，即根节点）void HPPop(HP* php){assert(php);assert(php->size > 0);swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size);}////3.将堆顶元素向下调整到满足堆特性为止//显示堆顶元素HPDataType HPTop(HP* php){assert(php);assert(php->size > 0);return php->a[0];}//是否为空bool HPEmpty(HP* php){assert(php);return php->size == 0;}//堆的大小int HPSize(HP* php){assert(php);return php->size;}
       
      Test.c
       
      #include"Heap.h"int main(){HP hp;int a[] = { 7,6,5,4,3,2,1 };HPInit(&hp);for (int i = 0; i  
      结果演示
        
      好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞吗，感谢看到这里，我们下篇博客见❤️