目录
一、头文件的声明
二、功能函数的实现
void Swap(HPDateType* pa, HPDateType* pb)；
void HPInit(HP* php)；
void HPDestory(HP* php)
bool HPEmpty(HP* php)
void AdjustUP(HPDateType* a, int child)
void AdjustDown(HPDateType* a, int n, int parent)
void HPPush(HP* php, HPDateType x)
void HPPop(HP* php)
int HPSize(HP* php)
HPDateType HPTop(HP* php)
三、注意点
一、头文件的声明
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDateType;
typedef struct heap
{
int size;
int capacity;
HPDateType* a;
}HP;
void Swap(HPDateType* pa, HPDateType* pb);
//固定
void HPInit(HP* php);
void HPDestory(HP* php);
bool HPEmpty(HP* php);
//算法
void AdjustUP(HPDateType* a, int child);
void AdjustDown(HPDateType* a, int n, int parent);
//Push、Pop
void HPPush(HP* php, HPDateType x);
void HPPop(HP* php);
//特殊元素
int HPSize(HP* php);
HPDateType HPTop(HP* php);二、功能函数的实现
void Swap(HPDateType* pa, HPDateType* pb)；
void Swap(HPDateType* pa, HPDateType* pb)
{
assert(pa);
HPDateType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void HPInit(HP* php)；
void HPInit(HP* php)
{
assert(php); //别忘了assert
php->a = NULL;
php->capacity = 0;
php->size = 0;
}void HPDestory(HP* php)
void HPDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}bool HPEmpty(HP* php)
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
void AdjustUP(HPDateType* a, int child)
void AdjustUP(HPDateType* a, int child)
{
assert(a);
int parent = (child - 1) / 2;
while (child > 0)
{
if (parent > 0 && a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//迭代
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}void AdjustDown(HPDateType* a, int n, int parent)
void AdjustDown(HPDateType* a, int n, int parent)
{
assert(a);
//建大堆：假设左孩子大
int child = parent * 2 + 1; //先× 2，再 + 1
while (child < n) //n是大小，不是下标
{
//向下调整需要找大孩子
if (child + 1 < n
&& a[child + 1] < a[child])
{
child++; //变成右孩子
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
//在循环中，让parent与child不断迭代
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}void HPPush(HP* php, HPDateType x)
1.判断是否满 ------ 开辟空间
开辟完成之后，需要capacity更新，空间更新
//void初始化，一级指针，没法开辟空间
{
assert(php);
//空间：都用realloc
if (php->capacity == php->size)
{
int newcapacity = php->capacity == 0 ? 4 : 2 * (php->capacity);
HPDateType* tmp = (HPDateType*)realloc(php->a, sizeof(HPDateType) * newcapacity);
if (tmp == NULL) //判断是否开辟失败
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newcapacity; //除了空火箭开辟，开需要对php->capacity进行修改
}
//size是结构元素 ， php->size才合法
php->a[php->size] = x;
php->size++;
AdjustUP(php->a, php->size - 1); //size是结构元素 ， php->size才合法
}void HPPop(HP* php)
1.头尾交换
2.删除数据
3.向下调整
void HPPop(HP* php)
{
assert(php);
assert(!HPEmpty(php)); //调用函数需要传参
Swap(php->a, &php->a[php->size - 1]);
php->size--; //size是结构体成员
AdjustDown(php->a, php->size, 0); //php->size 需要传数组的大小
}int HPSize(HP* php)
int HPSize(HP* php)
{
assert(php);
return php->size;
}HPDateType HPTop(HP* php)
HPDateType HPTop(HP* php)
{
assert(php);
assert(!HPEmpty(php)); //内部调用函数，需要传参！！！
return php->a[0];
}三、注意点
需要注意的是，在函数内部调用HPEmpty函数时，需要传参！
