定义

typedef int HPDataType;typedef struct Heap {HPDataType* a;//用数组存数据int size;//当前数组存放数据的数量int capacity;//数组容量}HP;

即将要实现的功能

void HPInit(HP* php);//初始化
void HPPush(HP* php, HPDataType x);//堆尾插入数据（数组尾部插入）
void HPPop(HP* php);//删除根结点
void HPDestroy(HP* php);//销毁堆
HPDataType HPTop(HP* php);//获取根结点
bool HPEmpty(HP* php);//判断堆是否为空void Swap(HPDataType* p1, HPDataType* p2);//交换*p1和*p2的值
void AdjustUp(HPDataType* a, int child);//向上调整建堆
void AdjustDown(HPDataType* a, int n, int parent);//向下调整建堆

交换函数（为后续做准备）

void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp = *p1;*p1 = *p2;*p2 = temp;
}

向上调整（建小堆）

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;//小心parent<0,在while循环中用child>0这个条件比较保险【（0-1）/2=0】}else {break;}}
}

具体是如何操作的呢，给大家画个图理解一下

经过AdjustUp之后变成

向下调整

void AdjustDown(HPDataType* a, int n, int parent)//最小的元素在堆顶
{int child = 2 * parent + 1;//左孩子while (child<n){if (a[child] > a[child + 1] && child+1 < n) {//防止右孩子越界++child;//找到最小的左or右孩子,待会要与父节点交换}if (a[child] < a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else {break;}}

咱们继续举例来理解一下

在上图这棵树中，我们要建小堆，但是我们可以发现，5结点小于6节点，所以5、6节点的位置要互换。

经过AdjustDown之后，变成

初始化

void HPInit(HP* php)
{assert(php);//断言，若php为空就会报错php->a = NULL;//数组置空//统统置0php->capacity = 0;php->size = 0;
}

堆的插入

void HPPush(HP* php, HPDataType x) {assert(php);
//判断数组是不是放满了，满了就扩容if (php->capacity == php->size) {
//运用三目运算符int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* temp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
//判断扩容是否成功if (temp == NULL) {perror("realloc fail!");return;}
//程序往下运行就扩容成功啦php->a = temp;php->capacity = newcapacity;}
//实现插入（在数组末尾插入）php->a[php->size] = x;
//szie++是为了下次插入数据php->size++;
//将新插入的数据调整到二叉树的正确位置中AdjustUp(php->a, php->size - 1);
}

堆的删除

删除从堆顶开始

​
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);//复位，把合适的堆顶元素放上来}​

获取堆顶元素

HPDataType HPTop(HP* php) {assert(php);assert(php->size > 0);return php->a[0];
}

判断堆是否为空

bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

堆的销毁

void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}