数据结构初阶——二叉树之——堆的实现
1.总代码
1.1头文件
#pragmaonce#include<stdio.h>#include<assert.h>#include<stdbool.h>#include<stdlib.h>typedefintHPDataType;typedefstructHeap{HPDataType*arr;intsize;intcapacity;}HP;voidSwap(HPDataType*p1,HPDataType*p2);voidAdjustUp(HPDataType*arr,intchild);voidAdjustDown(HPDataType*arr,intnums,intparent);voidHPInit(HP*php);voidHPDestroy(HP*php);voidHPPush(HP*php,HPDataType data);voidHPPop(HP*php);HPDataTypeHPTop(HP*php);boolHPEmpty(HP*php);1.2源文件
#define_CRT_SECURE_NO_WARNINGS1#include"Heap.h"voidSwap(HPDataType*p1,HPDataType*p2){HPDataType tmp=*p1;*p1=*p2;*p2=tmp;}HPDataTypeHPTop(HP*php){assert(php);assert(php->size>0);returnphp->arr[0];}voidAdjustUp(HPDataType*arr,intchild){intparent=(child-1)/2;while(child>0){if(arr[child]<arr[parent]){Swap(&arr[child],&arr[parent]);child=parent;parent=(child-1)/2;}else{break;}}}voidAdjustDown(HPDataType*arr,intnums,intparent){intchild=(parent*2)+1;while(child<nums){if(child+1<nums&&arr[child+1]<arr[child]){child++;}//找到要交换的孩子if(arr[child]<arr[parent]){Swap(&arr[child],&arr[parent]);parent=child;child=(parent*2)+1;}else{break;}}}voidHPInit(HP*php){assert(php);php->arr=NULL;php->capacity=php->size=0;}voidHPDestroy(HP*php){assert(php);free(php->arr);php->arr=NULL;php->capacity=php->size=0;}voidHPPush(HP*php,HPDataType data){assert(php);if(php->capacity==php->size){intnewcapacity=php->capacity==0?4:(php->capacity)*2;HPDataType*tmp=(HPDataType*)realloc(php->arr,newcapacity*sizeof(HPDataType));if(tmp==NULL){perror("realloc fail");return;}//扩容成功php->arr=tmp;php->capacity=newcapacity;}php->arr[php->size]=data;php->size++;AdjustUp(php->arr,php->size-1);}voidHPPop(HP*php){assert(php);assert(php->size>0);Swap(&php->arr[0],&php->arr[php->size-1]);php->size--;AdjustDown(php->arr,php->size,0);}boolHPEmpty(HP*php){assert(php);returnphp->size==0;}#define_CRT_SECURE_NO_WARNINGS1#include"Heap.h"//int main()//{// int arr[] = { 4,200,1,8,5,10,6,77,100 };// HP hp;// HPInit(&hp);// int j = sizeof(arr) / sizeof(arr[0]);// for(int i = 0;i < j;i++)// {// HPPush(&hp,arr[i]);// }// while (!HPEmpty(&hp))// {// printf("%d ", HPTop(&hp));// HPPop(&hp);// }// HPDestroy(&hp);// return 0;//}//void HeapSort(int* a, int n)//{// // 降序，建小堆// // 升序，建大堆// /*for (int i = 1; i < n; i++)// {// AdjustUp(a, i);// }*///// for (int i = (n - 1 - 1) / 2; i >= 0; i--)// {// AdjustDown(a, n, i);// }//// int end = n - 1;// while (end > 0)// {// Swap(&a[0], &a[end]);// AdjustDown(a, end, 0);// --end;// }voidHeapSort(int*a,intn){// 降序，建小堆// 升序，建大堆/*for (int i = 1; i < n; i++) { AdjustUp(a, i); }*//*for (int i = 1; i < n; i++) { AdjustUp(a, i); }*/for(inti=(n-1-1)/2;i>=0;i--){AdjustDown(a,n,i);}intend=n-1;while(end>0){Swap(&a[0],&a[end]);AdjustDown(a,end,0);--end;}}voidTestHeap2(){inta[]={4,2,8,1,5,6,9,7,2,7,9};HeapSort(a,sizeof(a)/sizeof(int));}intmain(){intarr[]={4,200,1,8,5,10,6,77,100};HP hp;HPInit(&hp);intj=sizeof(arr)/sizeof(arr[0]);for(inti=0;i<j;i++){HPPush(&hp,arr[i]);}while(!HPEmpty(&hp)){printf("%d ",HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);TestHeap2();return0;}2.堆的实现
2.1HPInit 函数
voidHPInit(HP*php){assert(php);php->arr=NULL;php->capacity=php->size=0;}功能：初始化堆结构体，置空。
用途：在使用堆前必须调用，设置初始状态。
2.2HPDestroy 函数
voidHPDestroy(HP*php){assert(php);free(php->arr);php->arr=NULL;php->capacity=php->size=0;}功能：释放堆占用的动态内存，并将指针置空，大小归零。
用途：堆使用完毕后调用，防止内存泄漏。
2.3HPPush函数（插入元素）
voidHPPush(HP*php,HPDataType data){assert(php);if(php->capacity==php->size){intnewcapacity=php->capacity==0?4:(php->capacity)*2;HPDataType*tmp=(HPDataType*)realloc(php->arr,newcapacity*sizeof(HPDataType));if(tmp==NULL){perror("realloc fail");return;}//扩容成功php->arr=tmp;php->capacity=newcapacity;}php->arr[php->size]=data;php->size++;AdjustUp(php->arr,php->size-1);}功能：向堆中插入一个新元素。
步骤：
- 检查容量是否已满，若满则扩容（初始容量0时设为4，否则翻倍）。
- 使用 realloc 调整内存，若失败则打印错误并返回。
- 将新元素放入数组末尾（下标 size）。
- size 加1。
- 调用 AdjustUp 从新元素位置开始向上调整，保持堆性质。
2.4 HPPop 函数（删除堆顶）
voidHPPop(HP*php){assert(php);assert(php->size>0);Swap(&php->arr[0],&php->arr[php->size-1]);php->size--;AdjustDown(php->arr,php->size,0);}功能：删除堆顶元素（即当前最小或最大）。
步骤：
- 断言堆非空。
- 交换堆顶（下标0）和最后一个元素（下标 size-1）。
- size 减1，逻辑上删除了原堆顶（现在在末尾，不再视为堆的一部分）。
- 从新的根（下标0）开始向下调整，恢复堆性质。
2.5 HPEmpty 函数
boolHPEmpty(HP*php){assert(php);returnphp->size==0;}- 功能：判断堆是否为空，空返回 true，否则 false。
2.6 Swap 函数
voidSwap(HPDataType*p1,HPDataType*p2){HPDataType tmp=*p1;*p1=*p1;*p2=tmp;}- 功能：交换两个 HPDataType 变量的值。
- 用途：在堆调整中频繁使用，用于交换父子节点。
2.7 HPTop 函数
HPDataTypeHPTop(HP*php){assert(php);assert(php->size>0);returnphp->arr[0];}功能：返回堆顶元素（最小或最大，取决于堆的性质，这里是小堆，因为 AdjustUp 和 AdjustDown 中使用 < 比较）。
用途：获取当前堆中优先级最高的元素（不删除）。
参数检查：断言确保指针非空且堆非空，防止空指针或空堆访问
2.8 AdjustUp 函数（向上调整）
voidAdjustUp(HPDataType*arr,intchild){intparent=(child-1)/2;while(child>0){if(arr[child]<arr[parent]){Swap(&arr[child],&arr[parent]);child=parent;parent=(child-1)/2;}else{break;}}}功能：将下标为 child 的元素向上调整，直到满足小堆性质（父节点小于等于子节点）。
用途：在插入新元素时，新元素放在数组末尾，然后向上调整到合适位置。
解释：
- int parent = (child - 1) / 2; 计算父节点下标。
- while (child > 0) 当孩子不是根节点时继续循环。
- if (arr[child] < arr[parent]) 如果孩子小于父节点（小堆要求），则交换。
- 交换后，更新 child 为原父节点，重新计算 parent，继续向上检查。
- 如果孩子不小于父节点，则已经满足堆性质，跳出循环。
2.9 AdjustDown 函数（向下调整）
voidAdjustDown(HPDataType*arr,intnums,intparent){intchild=(parent*2)+1;while(child<nums){if(child+1<nums&&arr[child+1]<arr[child]){child++;}//找到要交换的孩子if(arr[child]<arr[parent]){Swap(&arr[child],&arr[parent]);parent=child;child=(parent*2)+1;}else{break;}}}功能：从下标 parent 开始向下调整，使子树满足小堆性质。nums 是当前堆的有效元素个数（防止越界）。
用途：删除堆顶时，将最后一个元素移到堆顶后，向下调整；或建堆时从非叶子节点开始调整。
解释：
- int child = parent * 2 + 1; 计算左孩子下标。
- while (child < nums) 当左孩子存在时循环。
- if (child + 1 < nums && arr[child + 1] < arr[child])
如果右孩子存在且小于左孩子，则选右孩子（即选择较小的孩子）。 - 之后 if (arr[child] < arr[parent]) 如果选中的孩子小于父节点，则交换。
- 交换后，更新 parent 为当前孩子，重新计算 child，继续向下调整。
- 否则跳出循环。
3.测试
3.1测试1
intmain(){intarr[]={4,200,1,8,5,10,6,77,100};HP hp;HPInit(&hp);intj=sizeof(arr)/sizeof(arr[0]);for(inti=0;i<j;i++){HPPush(&hp,arr[i]);}while(!HPEmpty(&hp)){printf("%d ",HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);return0;}用途：测试堆的基本功能。
先初始化堆，然后循环插入数组元素。
再不断弹出堆顶并打印，由于是小堆，每次弹出最小值，因此输出应为升序序列。
最后销毁堆
3.2测试2（堆排序函数 HeapSort）
//小堆voidHeapSort(int*a,intn){for(inti=(n-1-1)/2;i>=0;i--){AdjustDown(a,n,i);}intend=n-1;while(end>0){Swap(&a[0],&a[end]);AdjustDown(a,end,0);--end;}}功能：对数组 a 进行堆排序（原地排序）。
建堆部分：采用向下调整建堆，从最后一个非叶子节点开始（(n-1-1)/2 即 n/2 - 1），直到根。时间复杂度 O(n)。
排序部分：while (end > 0) 循环，每次将堆顶（当前最小值）与下标 end 的元素交换，然后对前 end 个元素重新向下调整，end 减1。最终数组变为降序（因为最小值依次放到了末尾）。
或者在这里我们话可以去向上调整，不过这样效率可能会比较慢，如下：
voidHeapSort(int*a,intn){/*降序，建小堆 升序，建大堆*/for(inti=1;i<n;i++){AdjustUp(a,i);}intend=n-1;while(end>0){Swap(&a[0],&a[end]);AdjustDown(a,end,0);--end;}}voidTestHeap2(){inta[]={4,2,8,1,5,6,9,7,2,7,9};HeapSort(a,sizeof(a)/sizeof(int));}intmain(){TestHeap2();return0;}代码流程分析：
建堆：for (int i = 1; i < n; i++) AdjustUp(a, i);
从第二个元素开始逐个向上调整，使整个数组成为一个小堆（因为 AdjustUp 使用 < 比较）。排序：while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end–; }
每次将堆顶（当前最小值）交换到末尾，然后对前 end 个元素向下调整，重复直到全部有序。
由于是小堆，最终数组是降序（从大到小）。向上调整建堆（时间复杂度 O(n log n)）
向下调整建堆（时间复杂度 O(n)）
我们可以再画图举个例子：
数组：[4,2,8,1,5]对应完全二叉树（下标从0开始）：
4(0)/\2(1)8(2)/\1(3)5(4)一、向上调整建小堆
我们从 i=1 到 i=4 依次调用 AdjustUp。
- i = 1（元素 2）
当前节点：下标1，值2，父节点下标0，值4。
因为 2 < 4，交换。交换后数组：[2, 4, 8, 1, 5]
树结构：
2(0)/\4(1)8(2)/\1(3)5(4)- i = 2（元素 8）
当前节点：下标2，值8，父节点下标0，值2。
8 < 2？否，不交换。
数组不变：[2, 4, 8, 1, 5]
树同上。
- i = 3（元素 1）
当前节点：下标3，值1，父节点下标1，值4。
1 < 4，交换 → [2, 1, 8, 4, 5]
新位置下标1，值1，父节点下标0，值2。1 < 2，交换 → [1, 2, 8, 4, 5]
新位置下标0，已是根，停止。
数组：[1, 2, 8, 4, 5]
树：
1(0)/\2(1)8(2)/\4(3)5(4)- i = 4（元素 5）
当前节点：下标4，值5，父节点下标1，值2。
5 < 2？否，不交换。
最终建堆完成：[1, 2, 8, 4, 5]（小堆）。
循环降序就不继续写了