堆（数据结构）——C语言

1.堆的概念与结构

⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性。如果有⼀个关键码的集合 0 1 K = {k ,k ,k ,... ， k } 2 式存储，在⼀个⼀维数组中，并满⾜： Ki<= K2∗i+1 （Ki>=K2*i+1且 Ki<=K2∗i+2 ）， i = 0 、 1 、 2... ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。

堆具有以下性质：

堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；

堆总是⼀棵完全⼆叉树。

这里还要利用一些二叉树的性质：

⼆叉树性质，对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：

若 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，否则无右孩子

2 堆的实现

依旧创建三个文件，heap.h,heap.c,test.c，分别为头文件，函数实现文件，测试文件

heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HDataType;typedef struct Head
{HDataType* arr;int size;int capacity;
}HD;void HDInit(HD* phd);
void HDDestory(HD* phd);void HDPush(HD* phd, HDataType x);
void HDPop(HD* phd);bool HDEmpty(HD* phd);
int HDSize(HD* phd);HDataType HDTop(HD* php);

结构体heap

这里底层结构使用数组，首先定义一个数组，这里数据类型依旧以int类型为例，为了便于修改，这里使用typedef为HDataType，size为数据个数，capacity为空间大小，（这里和前面顺序表的结构定义一模一样）。

创建堆void HDInit(HD* phd)

void HDInit(HD* phd)
{assert(phd);phd->arr = NULL;phd->size = phd->capacity = 0;
}

首先断言传的指针非空，创建堆，就是先将数组指针置为空，初始化元素个数和空间大小为0。

’销毁void HDDestory(HD* phd)

void HDDestory(HD* phd)
{assert(phd);if (phd->arr){free(phd->arr);phd->arr = NULL;}phd->capacity = phd->size = 0;
}

首先断言传的指针非空，如果数组指针为非空，就释放掉，置为空，再将空间大小和元素个数归为0。

插入元素void HDPush(HD* phd, HDataType x)

void HDPush(HD* phd, HDataType x)
{assert(phd);if (phd->size == phd->capacity){int newcapacity = phd->capacity == 0 ? 4 : phd->capacity * 2;HDataType* tmp = (HDataType*)realloc(phd->arr, sizeof(HDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!");exit(1);}phd->arr = tmp;phd->capacity = newcapacity;}phd->arr[phd->size] = x;Adjustup(phd->arr, phd->size);++phd->size;
}

首先断言传的指针非空，这里要插入，就要判断空间是否已满，当size和空间大小相等时，即空间已满，需要申请空间，这里申请空间大小，每次申请原来的两倍，这里如果空间大小为0，要进行特殊处理，直接赋给4个空间大小，注意还要判断是否申请成功，申请成功后，将值直接赋值给数组size位置，因为这里是堆，所以还要调整元素位置；

void Adjustup(HDataType* arr, int child)
{int parent = (child - 1) / 2;while (child){int tmp = 0;if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void Swap(HDataType* a, HDataType* b)
{HDataType c = *a;*a = *b;*b = c;
}

这里以大堆为例，这里从最后插入元素，所以要从下向上调整，首先就要寻找最后一个结点的双亲结点，和双亲结点进行比较，如果大于，就要进行交换，然后，向上移动将双亲结点赋给新的孩子结点，通过孩子结点找到，新的双亲结点，重复操作，直到孩子结点到达根节点，这里如果中途发现不满足大于，说明已经调整完了，可以直接break，跳出循环。

判断堆是否为空bool HDEmpty(HD* phd)

bool HDEmpty(HD* phd)
{assert(phd);return phd->size == 0;
}

首先断言传的指针非空，直接判断元素个数是否为0，如果为0，则堆为空，否则不为空。

取出根节点void HDPop(HD* phd)

void HDPop(HD* phd)
{assert(!HDEmpty(phd));Swap(&phd->arr[0],&phd->arr[phd->size - 1]);phd->size--;AdJustDown(phd->arr, 0, phd->size);
}

首先判断堆是否为空，为空则不能取出，这里利用一个思想，就是先将根节点，和最后一个结点交换位置，再从根节点向下调整堆，最后再将size减减，及取出最后一个，也就是根节点。

void AdJustDown(HDataType* arr, int parent, int n)
{int child = 2 * parent + 1;while (child< n){if (child + 1 < n&&arr[child] < arr[child + 1])//注意这里出现的访问越界，用child+1排除{child++;}if ( arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

这里向下调整，先通过双亲结点找到孩子结点，还需对两个孩子结点进行比较，这里以大堆为例，所以要将孩子结点较大的，与双亲结点进行比较，如果大于，就要进行交换，然后将孩子结点作为新的双亲结点，在通过新的双亲结点找到新的孩子结点，重复刚才的操作，直到孩子结点超出整个数组个数，中途如果出现不大于，说明调整完了，直接break跳出循环。

读出根节点HDataType HDTop(HD* phd)

HDataType HDTop(HD* phd)
{assert(!HDEmpty(phd));return phd->arr[0];
}

首先判断堆是否为空，为空则不能取出，直接返回数组第一个元素，即为根节点元素。

元素个数int HDSize(HD* phd)

int HDSize(HD* phd)
{assert(phd);return phd->size;
}

首先判断传的指针非空，直接返回结构体中size，即为元素个数。

整体代码：

heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HDataType;typedef struct Head
{HDataType* arr;int size;int capacity;
}HD;void HDInit(HD* phd);
void HDDestory(HD* phd);void HDPush(HD* phd, HDataType x);
void HDPop(HD* phd);bool HDEmpty(HD* phd);
int HDSize(HD* phd);HDataType HDTop(HD* php);

heap.c

#include"Head.h"void HDInit(HD* phd)
{assert(phd);phd->arr = NULL;phd->size = phd->capacity = 0;
}void HDDestory(HD* phd)
{assert(phd);if (phd->arr){free(phd->arr);phd->arr = NULL;}phd->capacity = phd->size = 0;
}bool HDEmpty(HD* phd)
{assert(phd);return phd->size == 0;
}int HDSize(HD* phd)
{assert(phd);return phd->size;
}void Swap(HDataType* a, HDataType* b)
{HDataType c = *a;*a = *b;*b = c;
}void Adjustup(HDataType* arr, int child)
{int parent = (child - 1) / 2;while (child){int tmp = 0;if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void HDPush(HD* phd, HDataType x)
{assert(phd);if (phd->size == phd->capacity){int newcapacity = phd->capacity == 0 ? 4 : phd->capacity * 2;HDataType* tmp = (HDataType*)realloc(phd->arr, sizeof(HDataType) * newcapacity);if (tmp == NULL){perror("realloc fail!");exit(1);}phd->arr = tmp;phd->capacity = newcapacity;}phd->arr[phd->size] = x;Adjustup(phd->arr, phd->size);++phd->size;
}void AdJustDown(HDataType* arr, int parent, int n)
{int child = 2 * parent + 1;while (child< n){if (child + 1 < n&&arr[child] < arr[child + 1])//注意这里出现的访问越界，用child+1排除{child++;}if ( arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HDPop(HD* phd)
{assert(!HDEmpty(phd));Swap(&phd->arr[0],&phd->arr[phd->size - 1]);phd->size--;AdJustDown(phd->arr, 0, phd->size);
}HDataType HDTop(HD* phd)
{assert(!HDEmpty(phd));return phd->arr[0];
}

test.c

#include"Head.h"
void test()
{HD hd;HDInit(&hd);HDPush(&hd, 1);HDPush(&hd, 2);HDPush(&hd, 3);HDPush(&hd, 4);HDPush(&hd, 5);HDPush(&hd, 6);HDPop(&hd);HDPop(&hd);HDDestory(&hd);
}
int main()
{test();return 0;
}