引言
顺序结构存储就是使⽤数组来存储，⼀般只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。
一、堆的概念
将一个元素集合k里，所有数据按照完成二叉树的顺序存储方式存储。
并且数组中的元素，满足以下关系
i = 0、1、2... ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆
叫做最⼩堆或⼩根堆。
文字的描述比较抽象，以下为图例
二、堆的性质
堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性：
• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；
• 堆总是⼀棵完全⼆叉树
而二叉树有具有以下性质：
1.若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点
2. 若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦
3. 若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦
由上述所知，我们可以通过堆的数组中的下标来搜索到其子节点与双亲结点，由此我们便可以实现二叉树的顺序存储，即堆的结构
三、堆的实现
堆的实现分为以下三个部分（这里我们实现的小堆）
1.定义堆的结构
同上所述，堆的实现使用的是二叉树的顺序存储结构，其底层依然是数组，所以与顺序表的定义大致类似。因此不过多赘述。
typedef int HPDatatype;
typedef struct Heap
{
HPDatatype* arr;
int size;
int capacity;
}HP;2.堆的初始化与销毁
基于顺序结构实现的堆，将指向堆的变量的地址传递过来使用一级指针接收，实现形参的改变影响到实参。
初始化堆，只需对其指针置空、空间大小和栈顶置0即可。
void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->capacity = php->size = 0;
}销毁堆：堆的空间是使用函数动态开辟的，那他得使用对应得free对空间进行释放，让后将堆的空间大小和，size置0即可。
void HPDestroy(HP* php)
{
assert(php);
if (php->arr)
free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}3.向上调整算法
堆中的数据有着严格的要求，而我们堆的底层是一个数组，往堆中插入数据一般是往数组的末端进行插入，但是插入之后堆的顺序就乱了，因此我们还需在插入数据之后对堆中的元素进行调整，使其重新变为一个堆，这其中对堆中的元素进行调整的算法，我们成为向上调整算法。
我们需要接收栈底层的数组，以及型加入的孩子节点的下标，将新插入的孩子节点与父亲节点进行比较大小，若孩子节点小于父亲节点就交换顺序，而新的父亲节点又是前一个节点的孩子节点，同样需要判断其大小，然后交换顺序，若父亲节点小于孩子节点的话就不需要继续循环下去使用break跳出。
因为后续还会频繁使用到交换结点的步骤，我们将其封装成一个函数Swap
void Swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}void Adjustup(HPDatatype* arr, int child)
{
int parent = (child - 1) / 2;
while (child>0)
{
if (arr[parent] >arr[child])
{
Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}4.堆的插入
首先需要判断一下有效数据个数（php->size）和空间大小是否相等，所以使用if语句，若两者想的，那么则说明需要扩容，否则不需要
在扩容操作首先需要判断当前的栈是否为空栈，若是空栈我们则需要先给其一片固定的空间大小，若不是空栈则继续扩容，因此我们使用三木操作符进行操作。
在开辟内存时一般使用realloc函数开辟，增容到原空间的2倍可以减少扩容操作的频率。如果每次只增加少量空间，那么在元素数量增长时，需要频繁进行扩容操作，这会降低性能。
若开辟成功则将temp赋给php->arr，以及空间大小的更新，否则打印报错信息。
而后就要插入的数据加入堆，此时新加入的数据处于我们的堆底，因此我们还需要调用向上调整算法--函数Adjustup
最后不要忘记堆的有效数据php->size++
void HPPush(HP* php, HPDatatype x)
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDatatype* temp = (HPDatatype*)realloc(php->arr, sizeof(HPDatatype) * newcapacity);
if(temp==NULL)
{
perror("realloc fail!");
exit(1);
}
php->arr = temp;
php->capacity = newcapacity;
}
php->arr[php->size] = x;
Adjustup(php->arr, php->size);
php->size++;
}5.向下调整算法
在出堆操作时，我们也不能随便出堆，否则堆里的元素就乱套了，我们一般出的是堆顶的元素，因为对顶的元素为堆中的极值。
但是我们该如何将堆顶的元素出堆呢，如果直接将后面的元素前移一位，那么堆的元素顺序则会乱套，所以我们选择将堆顶的元素与堆底的元素互换，在使得size--；这样我们便将堆顶的元素从堆底出堆，同时也保证了堆中的元素除了堆顶都未发生改变。
然而这样还不是一个真正的堆，因为此时我们的堆顶元素为原先的堆底，所以我们要实现一个操作，将堆顶元素进行调整使其重新变为一个堆
向上调整算法是向上找父亲节点，而向下调整算法是向下找孩子节点，通过传递过来的参数 parent 向下找孩子结点。
我们无法确定双亲结点的两个子节点谁大谁小，因此在对孩子节点与父亲节点比较大小交换之前需要比较左孩子节点和右孩子节点arr[child] > arr[child + 1]，若左孩子节点大于右孩子，那child就需要加1，同时为了防止child+1后不满足 child < n从而在后续的交换里导致数组越界访问，所以在if语句里还需要加上一条判断 child + 1 < n。
执行子节点与父节点交换的if语句里，在交换完两个节点后需要更新新的父节点，和子节点来比较，判断是否存在比新的父节点还小的值。最后若子节点大于父节点，那就说明不需要交换，使用break跳出循环即可。
void Adjustdown(HPDatatype* arr, int parent, int size)
{
int child = 2 * parent + 1;
while (child<size)
{
if (child+1<size && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}6.堆的删除
在第五点中我们便提到，堆的删除一般的为删除堆顶元素
首先我们需要将其堆底元素和堆顶元素进行交换，之后将php->size--实现元素的出堆，而后我们再使用向下调整算法进行堆的调整使其重新变为一个堆即可
void HPPop(HP* php)
{
assert(php);
assert(!HPEmpty(php));
Swap(&php->arr[0], &php->arr[php->size - 1]);
php->size--;
Adjustdown(php->arr, 0, php->size);
}7.取堆顶数据
HPDatatype HPTop(HP* php)
{
assert(php && php->size);
return php->arr[0];
}8.堆的有效数据个数
int HPSize(HP* php)
{
assert(php);
return php->size;
}四、源码
Heap.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDatatype;
typedef struct Heap
{
HPDatatype* arr;
int size;
int capacity;
}HP;
//堆的初始化
void HPInit(HP* php);
// 堆的销毁
void HPDestroy(HP* php);
//向上调整
void Adjustup(HPDatatype* arr, int child);
// 堆的插入
void HPPush(HP* php, HPDatatype x);
//堆的判空
bool HPEmpty(HP* php);
//向下调整
void Adjustdown(HPDatatype* arr, int parent, int size);
// 堆的删除
void HPPop(HP* php);
// 取堆顶的数据
HPDatatype HPTop(HP* php);
// 堆的数据个数
int HPSize(HP* php);Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void HPInit(HP* php)
{
assert(php);
php->arr = NULL;
php->capacity = php->size = 0;
}
void HPDestroy(HP* php)
{
assert(php);
if (php->arr)
free(php->arr);
php->arr = NULL;
php->capacity = php->size = 0;
}
void Swap(int* x, int* y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void Adjustup(HPDatatype* arr, int child)
{
int parent = (child - 1) / 2;
while (child>0)
{
if (arr[parent] >arr[child])
{
Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HPPush(HP* php, HPDatatype x)
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDatatype* temp = (HPDatatype*)realloc(php->arr, sizeof(HPDatatype) * newcapacity);
if(temp==NULL)
{
perror("realloc fail!");
exit(1);
}
php->arr = temp;
php->capacity = newcapacity;
}
php->arr[php->size] = x;
Adjustup(php->arr, php->size);
php->size++;
}
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
void Adjustdown(HPDatatype* arr, int parent, int size)
{
int child = 2 * parent + 1;
while (child<size)
{
if (child+1<size && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HPPop(HP* php)
{
assert(php);
assert(!HPEmpty(php));
Swap(&php->arr[0], &php->arr[php->size - 1]);
php->size--;
Adjustdown(php->arr, 0, php->size);
}
HPDatatype HPTop(HP* php)
{
assert(php && php->size);
return php->arr[0];
}
int HPSize(HP* php)
{
assert(php);
return php->size;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void Testhp()
{
HP hp;
HPInit(&hp);
int arr[]= { 17,20,10,13,19,15,18,16};
for (int i = 0; i < 8; i++)
{
HPPush(&hp, arr[i]);
}
//HPPop(&hp);
for (int i = 0; i < hp.size; i++)
{
printf("%d ", hp.arr[i]);
}
//while (hp.size != 0)
//{
// printf("%d ", HPTop(&hp));
// HPPop(&hp);
//}
HPDestroy(&hp);
}
int main()
{
Testhp();
return 0;
}