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[i]);
}
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[php->size] = 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[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;//返回堆中数据个数
}
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[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;
}
我们可以来验证一下是不是堆
- 堆的向上调整和向下调整的代码一定要是匹配的，小堆的只能和小堆匹配使用，大堆的只能和大堆匹配使用，要不然就会让你十分抓马 ，我就是因为错误匹配使用就导致了痛苦了两个晚上……
- 还有就是大家一定要去画图去验证一下这个是不是堆，不要用眼睛看
- 其次就是一定要建好堆后再使用堆的向上调整和向下调整
