堆的基本操作（c语言实现）
1.堆的基本操作1.1界说堆
typedef int HPDataType;//堆中存储数据的类型
typedef struct Heap
{
HPDataType* a;//用于存储数据的数组
int size;//记录堆中已有元素个数
int capacity;//记录堆的容量
}HP;
1.2初始化堆
然后我们需要一个初始化函数，对刚创建的堆进行初始化，注意在初始化期间要将传入数据建堆。
//初始化堆
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);
}
}
1.3 烧毁堆
为了避免内存走漏，利用完动态开发的内存空间后都要及时开释该空间，以是，一个用于开释内存空间的函数是必不可少的。
//销毁堆
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);//释放动态开辟的数组
php->a = NULL;//及时置空
php->size = 0;//元素个数置0
php->capacity = 0;//容量置0
}
1.4打印堆
打印堆中的数据，这里用的打印格式是按照堆的物理布局进行打印，即打印为一排连续的数字。
//打印堆
void HeapPrint(HP* php)
{
assert(php);
//按照物理结构进行打印
int i = 0;
for (i = 0; i < php->size; i++)
{
printf("%d ", php->a);
}
printf("\n");
}
1.5堆的插入
数据插入时是插入到数组的末了，即树形布局的末了一层的末了一个结点，以是插入数据后我们需要运用堆的向上调解算法对堆进行调解，使其在插入数据后仍然保持堆的布局。
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 = x;
php->size++;
AdjustUp(php->a, php->size - 1);
} 这个插入的效果完全取决于AdjustUp函数是给大堆筹划的还是小堆！！
1.6堆的删除
堆的删除操作通常指的是从堆中移除最大值或最小值的操作。
在最大堆中，根节点是最大的元素，而在最小堆中，根节点是最小的元素。
以下是堆的删除操作的基本思绪：
[*]首先，将堆顶元素（即根节点）与末了一个元素互换位置，即将最大值或最小值移动到数组的末了。
[*] 然后，将堆的大小减1，即删除了原来堆顶的元素。
[*]末了，对新的堆顶元素进行向下调解，以保持堆的性子。在最大堆中，需要将新堆顶元素与其子节点中的较大者互换，直到满足最大堆的性子；在最小堆中，需要将新堆顶元素与其子节点中的较小者互换，直到满足最小堆的性子。
通过以上步骤，可以实现堆的删除操作，并保持堆的性子稳定。
//堆的删除
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a, &php->a);//交换堆顶和最后一个结点的位置
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;//返回堆中数据个数
}
1.8堆的判空
堆的判空，即判断堆布局体中的size变量是否为0。
//堆的判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;//判断堆中数据是否为0
}
2.完整操作加测试代码
#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 < a) { ++child; } if (a < a) { Swap(&a, &a); 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 < a)//孩子结点的值小于父结点的值 { //将父结点与孩子结点互换 Swap(&a, &a); //继承向上进行调解 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 = 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);
}
printf("\n");
}
void HeapPop(HP* php){ assert(php); assert(!HeapEmpty(php)); // 删除数据 Swap(&php->a, &php->a); php->size--; AdjustDown(php->a, php->size, 0);}HPDataType HeapTop(HP* php){ assert(php); return php->a;}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); HeapInit(&hp,a,size); HeapPrint(&hp); HeapPop(&hp); HeapPrint(&hp); HeapPush(&hp, 4); HeapPrint(&hp); return 0;} https://img-blog.csdnimg.cn/direct/a95ef8dcfec14a169dba327cfcde71ed.png
我们可以来验证一下是不是堆
https://img-blog.csdnimg.cn/direct/26729cf577e8426fb18fe993cfb39c34.jpeg
[*]堆的向上调解和向下调解的代码一定要是匹配的，小堆的只能和小堆匹配利用，大堆的只能和大堆匹配利用，要不然就会让你非常抓马 ，我就是因为错误匹配利用就导致了痛苦了两个晚上……
[*]另有就是大家一定要去绘图去验证一下这个是不是堆，不要用眼睛看
[*]其次就是一定要建好堆后再利用堆的向上调解和向下调解
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]