通过前几次的博客我们大致了解了堆的性质，接下来我们用数据结构来封装堆
注意本篇博客建堆建的是大堆。
首先建堆
typedef int HPDataType;
struct Heap
{
HPDataType* a; //数组
int size; //大小
int capacity; //容量
};
typedef struct Heap HP;?实现以下几种接口：
void HeapInit(HP* php, HPDataType* a, int n); //初始化
void HeapDestory(HP* php); //销毁
void HeapPush(HP* php, HPDataType x); //入一个数据，仍然是堆
void HeapPop(HP* php); // 删除
HPDataType HeapTop(HP* php); // 返回堆顶
int HeapSize(HP* php); // 统计大小
bool HEapEmpty(HP* php); //判断堆是否为空
void HeapPrint(HP* php); // 打印?初始化的实现
void HeapInit(HP* php, HPDataType* a, int n); //初始化形参中的HP* php,相当于是把结构体的地址给这个函数了，可以直接使用这个结构体
第一步：我们首先要给php 里面的数组开空间（也就是php->a）。
第二步我们要把我们自己创建的数组（HPDataType* a）的内容拷贝到php里面的数组中（也就是php->a）。
第三步进行建堆。
我们不直接对数组进行处理的原因是我们要把php->a 做成堆，并且待会还要支持插入，删除等操作，就必须是要自己malloc的，因为如果待会数组空间不够需要自己增容
拷贝有两种方式
第一种用个for循环
for (int i = 0;i < n;i++)
{
php->a[i] = a[i];
}
php->size = n;
php->capacity = n;第二种直接用，memcpy函数
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = n;
php->capacity = n;?接下来，建堆
for (int i = (php->size - 1 - 1) / 2;i >= 0;i--)
{
AdjustDown(php->a , php->size, i);
} 完整代码：
void HeapInit(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = n;
php->capacity = n;
for (int i = (php->size - 1 - 1) / 2;i >= 0;i--)
{
AdjustDown(php->a , php->size, i);
}
}?这里的AdjustDown（向下调整算法）之前已经实现过，现在不再赘述。
销毁的实现
释放掉php->a的空间，将大小size与容量置为0即可
void HeapDestory(HP* php)
{
assert(php);
free(php->a);
php->size = php->capacity = 0;
}?入数据的实现
首先检查下空间（php->a）是否足够不够就进行扩容，接着插入数据。
?因为堆的本质就是数组，插入一个数据，就是在数组最后加一个空间，增加一个数据
但是插入完数据后，还得要保证这个数组仍然是一个堆
如下图：
?对于第二种插入88 的情况，我们就需要将88 进行向上调整
思路就是，如果孩子比父母大就交换，交换之后，父母就成为新的孩子，依次循环，直到孩子到达初始位置，如果孩子比父母小，直接终止循环即可。
代码如下：
void Adjustup(int* 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;
}
}
}ps:如果建的是小堆，只需要吧大于改成小于即可?
完整代码如下：
void HeapPush(HP* php, HPDataType x)
{
if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
Adjustup(php->a, php->size - 1);
}?删除的实现
删除堆的一个数据，指的是删除堆顶的数据，
如果我们采用后面覆盖前面的方式删除，那么时间复杂度就是O(N),并且堆的结构都打乱了，还需要重新建堆又是O(N)，效率太低了
所以我们采用之前堆排序的思想，交换堆顶与堆底的数据，删除新的堆底的数据，然后进行一次向下调整，时间复杂度是O(logN)
代码如下：
void HeapPop(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);
}?返回堆顶实现
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
?统计堆中数据个数
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
?检测堆是否为空
bool HEapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}打印接口的实现
void HeapPrint(HP* php)
{
for (int i = 0;i < php->size;i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
int num = 0;
int level = 1;
for (int i = 0;i < php->size;i++)
{
printf("%d ", php->a[i]);
num++;
if (num == level)
{
printf("\n");
level *= 2;
num = 0;
}
}
printf("\n");
printf("\n");
}?完整代码及演示
Heap.h 部分
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef int HPDataType;
struct Heap
{
HPDataType* a; //数组
int size; //大小
int capacity; //容量
};
typedef struct Heap HP;
void Swap(int* p1, int* p2);
void AdjustDown(int* a, int n, int parent);
void Adjustup(int* a, int child);
//数组 数组大小
void HeapInit(HP* php, HPDataType* a, int n); //初始化
void HeapDestory(HP* php); //销毁
void HeapPush(HP* php, HPDataType x); //入一个数据，仍然是堆
void HeapPop(HP* php); // 删除
HPDataType HeapTop(HP* php); // 返回堆顶
int HeapSize(HP* php); // 统计大小
bool HEapEmpty(HP* php); //判断堆是否为空
void HeapPrint(HP* php); // 打印
Heap.c 部分
#include"Heap.h"
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustDown(int* 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[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else //b情况
{
break;
}
}
}
void Adjustup(int* 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 HeapInit(HP* php, HPDataType* a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
/*for (int i = 0;i < n;i++)
{
php->a[i] = a[i];
}*/
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = n;
php->capacity = n;
for (int i = (php->size - 1 - 1) / 2;i >= 0;i--)
{
AdjustDown(php->a , php->size, i);
}
}
void HeapDestory(HP* php)
{
assert(php);
free(php->a);
php->size = php->capacity = 0;
}
void HeapPush(HP* php, HPDataType x)
{
if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
Adjustup(php->a, php->size - 1);
}
void HeapPop(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);
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
bool HEapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
void HeapPrint(HP* php)
{
for (int i = 0;i < php->size;i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
int num = 0;
int level = 1;
for (int i = 0;i < php->size;i++)
{
printf("%d ", php->a[i]);
num++;
if (num == level)
{
printf("\n");
level *= 2;
num = 0;
}
}
printf("\n");
printf("\n");
}?Test.c部分
#include"Heap.h"
int main()
{
int a[] = { 15,18,28,34,65,19,49,25,37,27 };
int n = sizeof(a) / sizeof(a[0]);
HP hp;
HeapInit(&hp, a, n);
HeapPrint(&hp);
HeapPush(&hp, 8);
HeapPrint(&hp);
HeapPush(&hp, 888);
HeapPrint(&hp);
HeapPop(&hp);
HeapPrint(&hp);
HeapDestory(&hp);
}演示效果
?