马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
1.堆的基本操作
1.1界说堆
- typedef int HPDataType;//堆中存储数据的类型
- typedef struct Heap
- {
- HPDataType* a;//用于存储数据的数组
- int size;//记录堆中已有元素个数
- int capacity;//记录堆的容量
- }HP;
然后我们需要一个初始化函数，对刚创建的堆进行初始化，注意在初始化期间要将传入数据建堆。
- //初始化堆
- 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);
- }
- }
为了避免内存走漏，利用完动态开发的内存空间后都要及时开释该空间，以是，一个用于开释内存空间的函数是必不可少的。
- //销毁堆
- void HeapDestroy(HP* php)
- {
- assert(php);
- free(php->a);//释放动态开辟的数组
- php->a = NULL;//及时置空
- php->size = 0;//元素个数置0
- php->capacity = 0;//容量置0
- }
打印堆中的数据，这里用的打印格式是按照堆的物理布局进行打印，即打印为一排连续的数字。
- //打印堆
- void HeapPrint(HP* php)
- {
- assert(php);
- //按照物理结构进行打印
- int i = 0;
- for (i = 0; i < php->size; i++)
- {
- printf("%d ", php->a[i]);
- }
- printf("\n");
- }
数据插入时是插入到数组的末了，即树形布局的末了一层的末了一个结点，以是插入数据后我们需要运用堆的向上调解算法对堆进行调解，使其在插入数据后仍然保持堆的布局。
- 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);
- }
1.6堆的删除
堆的删除操作通常指的是从堆中移除最大值或最小值的操作。
在最大堆中，根节点是最大的元素，而在最小堆中，根节点是最小的元素。
以下是堆的删除操作的基本思绪：
- 首先，将堆顶元素（即根节点）与末了一个元素互换位置，即将最大值或最小值移动到数组的末了。
- 然后，将堆的大小减1，即删除了原来堆顶的元素。
- 末了，对新的堆顶元素进行向下调解，以保持堆的性子。在最大堆中，需要将新堆顶元素与其子节点中的较大者互换，直到满足最大堆的性子；在最小堆中，需要将新堆顶元素与其子节点中的较小者互换，直到满足最小堆的性子。
通过以上步骤，可以实现堆的删除操作，并保持堆的性子稳定。
- //堆的删除
- 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);//向下调整
- }
1. 首先，通过断言（assert）确保传入的堆指针（php）不为空，并且堆不为空。
2. 然后，将堆顶元素（索引为0的元素）与末了一个元素进行互换，即将堆顶元素移动到数组的末了。
3. 接着，将堆的大小减1，即删除了原来堆顶的元素。
4. 末了，调用AdjustDown函数对新的堆顶元素进行向下调解，以保持堆的性子。
1.7.获取堆的数据个数
获取堆的数据个数，即返回堆布局体中的size变量。
- //获取堆中数据个数
- int HeapSize(HP* php)
- {
- assert(php);
- return php->size;//返回堆中数据个数
- }
堆的判空，即判断堆布局体中的size变量是否为0。
- //堆的判空
- bool HeapEmpty(HP* php)
- {
- assert(php);
- return php->size == 0;//判断堆中数据是否为0
- }
- #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);}//打印堆
- void HeapPrint(HP* php)
- {
- assert(php);
- //按照物理结构进行打印
- int i = 0;
- for (i = 0; i < php->size; i++)
- {
- printf("%d ", php->a[i]);
- }
- printf("\n");
- }
- 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企服之家，中国第一个企服评测及商务社交产业平台。 |
