一 堆的基本概念：
1.堆的定义：
堆是一颗完全二叉树，这样实现的堆也被称为二叉堆,堆中节点的值都大于等于（或小于等于）其子节点的值
每个父节点的值都大于或等于其子节点的值，我们把它称为大顶堆
每个父节点的值都小于或等于其子节点的值，我们将其称为小顶堆。
二 完全二叉树和满二叉树：
1.满二叉树(FBT)：
每个节点要么有零个，要么有两个子节点。 这意味着没有节点恰好有一个子节点。
所有叶节点都在同一层。 这意味着所有叶节点的深度相等。
2.完全二叉树(CBT)：
除最后一层外，所有层都完全填充。 这意味着这些级别的每个节点恰好有两个子节点。
最后一层的节点都尽可能向左且连续。 这意味着没有节点应该在其左侧有一个空子节点，而右侧有一个非空子节点。
三 堆顺序存储：
1.堆的存储结构：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;2.堆的所有接口：
//初始化、销毁
void HPInit(HP* php);
void HPDestroy(HP* php);
// 插入
void HPPush(HP* php, HPDataType x);
//获取堆顶元素、堆的有效数据个数
HPDataType HPTop(HP* php);
HPDataType HPsize(HP* php);
// 删除堆顶的数据
void HPPop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);3.堆的初始化：
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
输出：
4.堆的销毁：
void HPDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}输出：
5.插入：
void HPPush(HP* php, HPDataType x)
{
assert(php);
//扩容数组
if (php->capacity == php->size)
{
HPDataType Newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* Ptmp = (HPDataType*)realloc(php->a , sizeof(HPDataType) * Newcapacity);
if (Ptmp == NULL)
{
perror("calloc error");
exit(-1);
}
php->a = Ptmp;
php->capacity = Newcapacity;
}
php->a[php->size] = x;
php->size++;
//向上调整
AdjustUp(php->a, php->size - 1); //因为php->size最后是指向最后数据的后面一个所以传要减一
}
输出：
6.向上调整(建小堆)：
void AdjustUp(HPDataType* a , HPDataType child)
{
HPDataType parents = (child - 1) / 2;//找父节点
while (child > 0)//当child走到首节点时就会停止循环
{
if (a[child] < a[parents])
{
Swap(&a[child] , &a[parents]);//交换数据
child = parents;
parents = (parents - 1) / 2;//改变父亲指针的指向，让父亲指针往上指
}
else
{
break;
}
}
}7.交换父子数据：
void Swap(HPDataType* x , HPDataType* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
当堆(小堆)要插入新数据时在逻辑层面上是在堆的最右下方插入一个值而在物理层面上是直接在添加在数组的后面，而我们插入一个值必然会改变小堆(大堆)的性质所以需要向上调整以此来保持，所以当插入32时首先需要找到父亲节点然后再跟它比下大小如果新插入的节点比它小那就需要调整，把数据互相交换然后让孩子指向父亲然后再让父亲指向父亲同时要查看数据的大小，当child小于0时就可以退出了
8.获取堆顶(最大或最小)的元素：
HPDataType HPTop(HP* php)
{
assert(php);
return php->a[0];
}输出：
9.获取堆的数据个数：
HPDataType HPsize(HP* php)
{
assert(php);
return php->size;
}输出：
10.删除堆顶的数据：
void HPPop(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);//向下调整
}输出：
虽然50 32还是显示但是我们靠自减已经将他们在逻辑层面给删除了但是再物理层面上还是带显示的
11.向下调整(逐个删除每个数据)：
void AdjustDown(HPDataType* a , HPDataType n , HPDataType parents)
{
HPDataType child = (parents * 2) + 1;
while (child < n)
{
//假设child指向左孩子
if (child + 1 < n && a[child] > a[child + 1])//选出左右孩子谁大谁小
{
child++;//如果右孩子小那就让child指针自增指向右孩指就行
}
if (a[child] < a[parents])
{
Swap(&a[child], &a[parents]);
child = parents;
child = (parents * 2) + 1;
}
else
{
break;
}
}
}
12.判断堆是否为空：
bool HPEmpty(HP* php)
{
assert(php);
if (php->size == 0)
{
return false;
}
return true;
//return php->size == 0;
}
输出：
13.打印堆：
