堆的基本操作（c语言实现）

 1.堆的基本操作

1.1界说堆

1. typedef int HPDataType;//堆中存储数据的类型
3. typedef struct Heap
4. {
5.         HPDataType* a;//用于存储数据的数组
6.         int size;//记录堆中已有元素个数
7.         int capacity;//记录堆的容量
8. }HP;

复制代码

1.2初始化堆

然后我们需要一个初始化函数，对刚创建的堆进行初始化，注意在初始化期间要将传入数据建堆。

1. //初始化堆
2. void HeapInit(HP* php, HPDataType* a, int n)
3. {
4.         assert(php);
6.         HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType)*n);//申请一个堆结构
7.         if (tmp == NULL)
8.         {
9.                 printf("malloc fail\n");
10.                 exit(-1);
11.         }
12.         php->a = tmp;
13.         memcpy(php->a, a, sizeof(HPDataType)*n);//拷贝数据到堆中
14.         php->size = n;
15.         php->capacity = n;
16.         int i = 0;
17.         //建堆
18.         for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
19.         {
20.                 AdjustDown(php->a, php->size, i);
21.         }
22. }

复制代码

1.3 烧毁堆

 为了避免内存走漏，利用完动态开发的内存空间后都要及时开释该空间，以是，一个用于开释内存空间的函数是必不可少的。

1. //销毁堆
2. void HeapDestroy(HP* php)
3. {
4.         assert(php);
6.         free(php->a);//释放动态开辟的数组
7.         php->a = NULL;//及时置空
8.         php->size = 0;//元素个数置0
9.         php->capacity = 0;//容量置0
10. }

复制代码

1.4打印堆

 打印堆中的数据，这里用的打印格式是按照堆的物理布局进行打印，即打印为一排连续的数字。

1. //打印堆
2. void HeapPrint(HP* php)
3. {
4.         assert(php);
5.         //按照物理结构进行打印
6.         int i = 0;
7.         for (i = 0; i < php->size; i++)
8.         {
9.                 printf("%d ", php->a[i]);
10.         }
11.         printf("\n");
12. }

复制代码

1.5堆的插入

 数据插入时是插入到数组的末了，即树形布局的末了一层的末了一个结点，以是插入数据后我们需要运用堆的向上调解算法对堆进行调解，使其在插入数据后仍然保持堆的布局。

1. void HeapPush(HP* php, HPDataType x)
2. {
3.         assert(php);
5.         if (php->size == php->capacity)
6.         {
7.                 HPDataType* tmp = (HPDataType*)realloc(php->a,
8.                          sizeof(HPDataType) * php->capacity*2);
9.                 if (tmp == NULL)
10.                 {
11.                         perror("realloc fail");
12.                         return;
13.                 }
14.                 php->a = tmp;
15.                 php->capacity *= 2;
16.         }
18.         php->a[php->size] = x;
19.         php->size++;
21.         AdjustUp(php->a, php->size - 1);
22. }

复制代码

 这个插入的效果完全取决于AdjustUp函数是给大堆筹划的还是小堆！！
1.6堆的删除

堆的删除操作通常指的是从堆中移除最大值或最小值的操作。
在最大堆中，根节点是最大的元素，而在最小堆中，根节点是最小的元素。
   以下是堆的删除操作的基本思绪：
  

• 首先，将堆顶元素（即根节点）与末了一个元素互换位置，即将最大值或最小值移动到数组的末了。
  
•  然后，将堆的大小减1，即删除了原来堆顶的元素。
  
• 末了，对新的堆顶元素进行向下调解，以保持堆的性子。在最大堆中，需要将新堆顶元素与其子节点中的较大者互换，直到满足最大堆的性子；在最小堆中，需要将新堆顶元素与其子节点中的较小者互换，直到满足最小堆的性子。
  

  通过以上步骤，可以实现堆的删除操作，并保持堆的性子稳定。

1. //堆的删除
2. void HeapPop(HP* php)
3. {
4.         assert(php);
5.         assert(!HeapEmpty(php));
7.         Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个结点的位置
8.         php->size--;//删除最后一个结点（也就是删除原来堆顶的元素）
9.         AdjustDown(php->a, php->size, 0);//向下调整
10. }

复制代码

这段代码是堆的删除操作，基本思绪如下：
1. 首先，通过断言（assert）确保传入的堆指针（php）不为空，并且堆不为空。
2. 然后，将堆顶元素（索引为0的元素）与末了一个元素进行互换，即将堆顶元素移动到数组的末了。
3. 接着，将堆的大小减1，即删除了原来堆顶的元素。
4. 末了，调用AdjustDown函数对新的堆顶元素进行向下调解，以保持堆的性子。

1.7.获取堆的数据个数

获取堆的数据个数，即返回堆布局体中的size变量。

1. //获取堆中数据个数
2. int HeapSize(HP* php)
3. {
4.         assert(php);
6.         return php->size;//返回堆中数据个数
7. }

复制代码

1.8堆的判空

堆的判空，即判断堆布局体中的size变量是否为0。

1. //堆的判空
2. bool HeapEmpty(HP* php)
3. {
4.         assert(php);
6.         return php->size == 0;//判断堆中数据是否为0
7. }

复制代码

2.完整操作加测试代码

1. #include<stdio.h>#include<assert.h>#include<stdlib.h>#include<stdbool.h>#include<time.h>typedef int HPDataType;typedef struct Heap{        HPDataType* a;        int size;        int capacity;}HP;void Swap(HPDataType* p1, HPDataType* p2){        HPDataType x = *p1;        *p1 = *p2;        *p2 = x;}//堆的向下调解（小堆）—— 左右子树都是小堆void AdjustDown(HPDataType* a, int n, int parent){        int child = parent * 2 + 1;        while (child < n)        {                // 选出左右孩子中大的那一个                if (child + 1 < n && a[child + 1] < a[child])                {                        ++child;                }                if (a[child] < a[parent])                {                        Swap(&a[child], &a[parent]);                        parent = child;                        child = parent * 2 + 1;                }                else                {                        break;                }        }}//初始化堆void HeapInit(HP* php, HPDataType* a, int n){        assert(php);        HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * n);//申请一个堆布局        if (tmp == NULL)        {                printf("malloc fail\n");                exit(-1);        }        php->a = tmp;        memcpy(php->a, a, sizeof(HPDataType) * n);//拷贝数据到堆中        php->size = n;        php->capacity = n;        int i = 0;        //建堆        for (i = (php->size - 1 - 1) / 2; i >= 0; i--)        {                AdjustDown(php->a, php->size, i);        }}bool HeapEmpty(HP* php){        assert(php);        return php->size == 0;}void HeapDestroy(HP* php){        assert(php);        free(php->a);        php->a = NULL;        php->capacity = php->size = 0;}//堆的向上调解（小堆）void AdjustUp(HPDataType* a, int child){        int parent = (child - 1) / 2;        while (child > 0)//调解到根结点的位置截止        {                if (a[child] < a[parent])//孩子结点的值小于父结点的值                {                        //将父结点与孩子结点互换                        Swap(&a[child], &a[parent]);                        //继承向上进行调解                        child = parent;                        parent = (child - 1) / 2;                }                else//已成堆                {                        break;                }        }}void HeapPush(HP* php, HPDataType x){        assert(php);        if (php->size == php->capacity)        {                HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);                if (tmp == NULL)                {                        perror("realloc fail");                        return;                }                php->a = tmp;                php->capacity *= 2;        }        php->a[php->size] = x;        php->size++;        AdjustUp(php->a, php->size - 1);}//打印堆
2. void HeapPrint(HP* php)
3. {
4.         assert(php);
5.         //按照物理结构进行打印
6.         int i = 0;
7.         for (i = 0; i < php->size; i++)
8.         {
9.                 printf("%d ", php->a[i]);
10.         }
11.         printf("\n");
12. }
13. void HeapPop(HP* php){        assert(php);        assert(!HeapEmpty(php));        // 删除数据        Swap(&php->a[0], &php->a[php->size - 1]);        php->size--;        AdjustDown(php->a, php->size, 0);}HPDataType HeapTop(HP* php){        assert(php);        return php->a[0];}int HeapSize(HP* php){        assert(php);        return php->size;}int main(){        HP hp;        int a[] = { 4,18,42,12,21,3,5,5,88,5,5,15,5,45,5 };        int size = sizeof(a) / sizeof(a[0]);        HeapInit(&hp,a,size);        HeapPrint(&hp);        HeapPop(&hp);        HeapPrint(&hp);        HeapPush(&hp, 4);        HeapPrint(&hp);        return 0;}

复制代码

我们可以来验证一下是不是堆

   

• 堆的向上调解和向下调解的代码一定要是匹配的，小堆的只能和小堆匹配利用，大堆的只能和大堆匹配利用，要不然就会让你非常抓马 ，我就是因为错误匹配利用就导致了痛苦了两个晚上……
  
• 另有就是大家一定要去绘图去验证一下这个是不是堆，不要用眼睛看
  
• 其次就是一定要建好堆后再利用堆的向上调解和向下调解
  

  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。