目录
1.堆删除函数HeapPop
一个常见的错误想法:挪动删除
正确方法
设计堆顶删除函数HeapPop
解析向下调整函数AdjustDown
核心思想
向下调整最多次数
向下调整的前提
代码实现
提问
细节分析
2.测试堆删除函数
运行结果
3.引申问题
运行结果
4.练习
分析
代码
执行过程图
运行结果
承接100.【C语言】数据结构之二叉树的堆实现 上文章
1.堆删除函数HeapPop
尾删没有任何意义,删头才有意义(即删堆顶),删除之后要调整二叉树,仍然符合大根堆的性质
拿上图举例,现删除堆顶元素50
一个常见的错误想法:挪动删除
即{50,30,8,5,12,0,2,15,3}变成{30,8,5,12,0,2,15,3}
将{30,8,5,12,0,2,15,3}画成二叉树会发现既不是大根堆也不是小根堆
此错误方法不仅效率低下还将父子兄弟之间的关系全部弄乱了
因此禁止使用挪动删除!
正确方法
让堆顶元素和数组的最后一个元素进行交换(Swap函数),接着删除最后一个元素(ps->size--),再向下调整
设计堆顶删除函数HeapPop
堆顶能删除的前提:堆不能是空的(调用HeapEmpty函数检验)
空堆检查函数HeapEmpty
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}交换函数Swap
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a,php->size,0);
}解析向下调整函数AdjustDown
核心思想
左孩子和右孩子哪一个大,parent就换哪个,重复前述步骤直到满足大根堆或小根堆的性质
以下面这个为例说明
经过两次向下调整后,变成大根堆
向下调整最多次数
最坏情况是调整到叶节点,即次
向下调整的前提
左右子树为堆
代码实现
一开始默认为左孩子,如果右孩子值大于左孩子,则进行调整
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else{break;}}
}提问
上述代码写的有没有问题?
答:if (a[child + 1] > a[child])有潜在的问题,可能会越界访问
child+1可能会大于或等于n
细节分析
改成下面这样行吗?
if (a[child + 1] > a[child] && child+1 < n)不行,要遵循&&的运算规则:先左后右,因此上方代码会先判断a[child + 1] > a[child]再判断child+1 < n,可能会先越界访问,之后判断child+1 < n就无效了
因此改为
if (child+1 < n && a[child + 1] > a[child])2.测试堆删除函数
main.c中写入以下代码,之后下断点至return 0;
#include "Heap.h"
int main()
{HP hp;HeapInit(&hp);HeapPush(&hp, 1);HeapPush(&hp, 3);HeapPush(&hp, 0);HeapPush(&hp, 5);HeapPush(&hp, 8);HeapPush(&hp, 12);HeapPush(&hp, 2);HeapPush(&hp, 5);HeapPush(&hp, 30);HeapPush(&hp, 50);while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}return 0;}备注:只要堆没有删空while (!HeapEmpty(&hp))就继续执行,这里要强调的点是:堆顶永远是堆中最大的数,因此只有删了堆顶,堆顶下面最大的数才能上去
运行结果
显然进行了堆排序
3.引申问题
若要打印上方排好序的堆中的前k个数(k<=n),代码怎么写?
答:稍加改动即可
int k = 0;scanf("%d", &k);while (!HeapEmpty(&hp)&&k--){printf("%d ", HeapTop(&hp));HeapPop(&hp);}运行结果
4.练习
给一个乱序数组,设计一个排序函数HeapSort,要求建立大根堆,写出代码
要求:不另外开辟空间
代码模板
??? HeapSort(??????)
{//??????
}int main()
{int arr[] = { 1,4,2,5,7,2,6,8,9,2 };HeapSort(??????);return 0;
}分析
在无序堆(既不是大根堆也不是小根堆)上建立大根堆,则需要对数组中的每一个元素进行向上调整
,则可写循环
代码
向上调整建堆
void HeapSort(int* arr, int n)
{for (int i = 1; i < n; i++){AdjustUp(arr, i);}
}
int main()
{int arr[] = { 1,4,2,5,7,2,6,8,9,2 };int size = sizeof(arr)/sizeof(arr[0]);HeapSort(arr,size);return 0;
}执行过程图
运行结果
5.堆的销毁函数HeapDestory
先释放内存,再设置结构体成员变量
void HeapDestory(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}
