目录一.创建堆结构二.堆的初始化三.数据入堆四.数据向上调整五.堆判空六.数据出堆七.数据向下调整八.取堆顶元素九.堆的元素个数十.堆销毁堆本质是完全二叉树一般用数组存储分为大堆、小堆常用来做堆排序、TopK 问题。一.创建堆结构堆结构成员的结构体应该包括:存储数据的数组arr,堆的当前存储容量capacity,堆当前的长度size。因此我们创建Heap结构体类型时应由一个数组及两个整型组成.typedef类定义的作用是方便后续使用堆时对存储的数据类型做更改。代码如下//堆的结构 typedef int HPDataType; typedef struct Heap { HPDataType* arr; int size; //有效数据个数 int capacity; //空间大小 }HP;二.堆的初始化堆的创建和初始化代码和顺序表相同因为底层结构都是数组。将数组置为空size和capacity在初始化阶段都为0即可。代码如下//初始化 void HPInit(HP* php) { php-arr NULL; php-size php-capacity 0; }三.数据入堆入堆的思路是:先判断堆的容量是否需要进行扩容。入堆逻辑和顺序表插入元素相同,都是直接按下标给堆尾赋值。赋值结束后同样需要给堆长度1。由于数据入堆以后堆大概率就不是真正的”大堆”或“小堆”了即堆顶数据不一定是最大或最小所以需要调整数据的排列方式考虑到数据是在堆尾插入所以将数据向上调整。代码如下//调整 void Swap(int* x, int* y) { int tmp *x; *x *y; *y tmp; } //数据入堆 void HPPush(HP* php, HPDataType x) { assert(php); //判断空间是否足够 if (php-size php-capacity) { int newCapcity php-capacity 0 ? 4 : 2 * php-capacity; HPDataType* tmp (HPDataType*)realloc(php-arr, newCapcity*sizeof(HPDataType)); if (tmp NULL) { perror(realloc fail!); exit(1); } php-arr tmp; php-capacity newCapcity; } php-arr[php-size] x; //向上调整 AdjustUp(php-arr, php-size); php-size; }四.数据向上调整堆和顺序表不同的点就在于顺序表插入元素后size就结束了但数据入堆后需要向上调整因为不能保证新入的元素一定完全符合堆定义的要求所以将数据向上调整。向上调整总得有个起始位置以插入位置为起始位置孩子节点。顺序存储结构存储完全二叉树时双亲结点和左右孩子的下标关系:parent(child-1)/2leftchildparent*21rightchildparent*22通过这几个公式,我们就可以很方便的在堆里对双亲和孩子结点进行调整.代码如下void Swap(int* x, int* y) { int tmp *x; *x *y; *y tmp; } //数据向上调整 void AdjustUp(HPDataType* arr, int child) { int parent (child - 1) / 2; while (child 0) { //大堆 //小堆 if (arr[child] arr[parent]) { //调整 Swap(arr[child], arr[parent]); child parent; parent (child - 1) / 2; } else { break; } } }五.堆判空在判空时只需要判断size是否等于0即可。代码如下// 判空 bool HPEmpty(HP* php) { assert(php); return php-size 0; }六.数据出堆顺序表尾删直接size--就可以但是堆和顺序表不同出堆只能出堆顶的数据。由于堆顶是堆数据的最值删除堆顶数据就会改变堆的性质所以在出堆操作时将堆顶数据和堆size-1位置的数据交换然后size--这样就将原来堆顶的数据为出堆了。size-1位置的数据换上后改变了堆的性质考虑到发生位置是在堆顶所以向下调整堆。代码如下//数据出堆 void HPPop(HP* php) { assert(!HPEmpty(php)); // 0 php-size-1 Swap(php-arr[0], php-arr[php-size - 1]); --php-size; //向下调整 AdjustDown(php-arr, 0, php-size); }七.数据向下调整当堆结构是大堆。向上调整需要要比较兄弟节点的数据大小只需要比较孩子节点和父节点的大小。向下调整与向上调整不同需要将待调整结点与其左右孩子比较若孩子大于该结点则选取值最大的孩子与该结点交换交换后对被交换下去的结点继续向下调整直至到达叶子结点或者该结点的值大于等于两个孩子结点的值向下调整结束。代码如下//向下调整算法 void AdjustDown(HPDataType* arr, int parent, int n) { int child parent * 2 1;//左孩子 while (child n) { //大堆 //小堆 if (child 1 n arr[child] arr[child 1]) { child; } //大堆: //小堆 if (arr[child] arr[parent]) { //调整 Swap(arr[child], arr[parent]); parent child; child parent * 2 1; } else { break; } } }八.取堆顶元素取堆顶元素就是访问数组首元素即size为0时的元素。代码如下//取堆顶数据 HPDataType HPTop(HP* php) { assert(!HPEmpty(php)); return php-arr[0]; }九.堆的元素个数和判空部分一样,直接访问size并返回即可。代码如下//求size int HPSize(HP* php) { assert(php); return php-size; }十.堆销毁在堆使用结束后我们需要将之前动态开辟的内存还给操作系统并将其指针置空size和capacity置为0。代码如下void HPDestroy(HP* php) { if (php-arr) free(php-arr); php-arr NULL; php-size php-capacity 0; }希望这篇堆的C语言实现详解能对大家有所帮助。