目录
堆的基本知识
堆（Heap）是一种特殊的树状数据结构。
主要特性
- 堆通常是一棵完全二叉树。
- 堆中的每一个节点必须满足特定顺序要求，以这个要求分出大根堆和小根堆。
大根堆：任何一个父节点的值都大于或等于它的子节点的值。
小根堆：任何一个父节点的值都小于或等于它的子节点的值。
基本操作
- 插入（Insertion）：在堆中添加新素，同时保持堆的属性。
- 删除（Deletion）：通常指的是删除堆顶素，然后重新调整堆以保持其属性。
- 查找堆顶素（Find Top）：在最大堆中找到最大素，在最小堆中找到最小素。
- 堆调整（Heapify）：将堆的某一部分重新调整，以恢复堆属性。
应用场景
- 优先级队列
- 堆排序
- 内存管理
实现方式
- 一般用数组实现
父子节点之间的索引：
1.父节点：i
2.左节点：2 * i + 1
3.右节点 2 * i + 2
4通过子节点i 找父节点 （i - 1）/ 2
堆的实现
堆的定义
typedef int HPDataType; typedef struct Heap { HPDataType* arr; int size; int capacity; }HP;跟我们定义顺序表类似，一个动态申请的数组、有效数据个数、最大可容纳数据个数。
堆的初始化
将arr置空，将capacity和size置0。
//堆的初始化 void HPInit(HP* php) { assert(php); php->arr = NULL; php->capacity = php->size = 0; }堆的销毁
将动态申请的数组free掉，把capacity和size置0。
// 堆的销毁 void HPDestroy(HP* php) { assert(php); free(php->arr); php->capacity = php->size = 0; } 堆的调整
调整算法用于堆的插入和删除后恢复堆的属性，但是用调整算法的前提是堆原本是有序的（大根堆或者小根堆）
向上调整
首先算出parent的索引，parent跟child比较，若child大于parent，则交换，然后更新parent、child，直到child小于等于0或者child小于parent了。
void AdjustUp(HPDataType* arr, int child) { assert(arr); int parent = (child - 1) / 2; while(child > 0)// parent >= 0 是错的 parent = (0 - 1) / 2 == 0 { if (arr[child] > arr[parent]) { //交换 Swap(&arr[child], &arr[parent]); child = parent; parent = (child - 1) / 2; } else { break;; } } } 注意，循环条件不能用parent >= 0来判断，因为当child = 1，parent = 0时，child = parent后，child = 0，然后parent = (0 - 1) / 2 == 0,达不到理想终止的效果。（虽然最后循环也能停止，因为循环里arr[child] > arr[parent]不成立，break掉了，但是代码还是有问题的，要改正）
向下调整
向下调整与向上调整是类似的，但也有区别。
以大根堆为例，需要先找到左右孩子中较大的一个，再跟父亲比较。
//向下调整 void AdjustDown(HPDataType* arr, int size, int parent) { assert(arr); int child = 2 * parent + 1; while (child < size) { //找两个孩子中较大的孩子 假设法 大的那个是左孩子 if (child + 1 < size && arr[child] < arr[child + 1]) { child++; } if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child; child = 2 * parent + 1; } else { break; } } }堆的插入
堆的插入只能尾插，不能随便插入到其他位置。
插入数据后使用向上调整恢复堆的属性。
//检查空间是否足够 void CheckCapacity(HP* php) { assert(php); if (php->capacity == php->size) { int NewCapacity = (php->capacity == 0 ? 4 : 2 * php->capacity); HPDataType* tep = (HPDataType*)realloc(php->arr, NewCapacity * sizeof(HPDataType)); if (tep == NULL) { perror("realloc fail!"); return; } php->arr = tep; php->capacity = NewCapacity; } } // 堆的插入 void HPPush(HP* php, HPDataType x) { assert(php); //插入之前检查空间是否足够 CheckCapacity(php); php->arr[php->size++] = x; AdjustUp(php->arr, php->size-1); }堆的删除
堆的删除是删除堆顶的数据，首先将堆顶数据和最后一个数据交换，让size--，然后使用向下调整算法恢复堆的属性。
// 堆的删除 删除堆顶数据 //堆顶与尾交换 size-- 然后向下调整 void HPPop(HP* php) { assert(php); assert(php->size > 0); Swap(&php->arr[0], &php->arr[--php->size]); AdjustDown(php->arr, php->size, 0); }取堆顶的数据
注意判断堆不为空就行了。
//取堆顶的数据 HPDataType HPTop(HP* php) { assert(php); assert(php->size > 0); return php->arr[0]; }堆的判空
判断size == 0就行。
//堆的判空 bool HPEmpty(HP* php) { assert(php); return php->size == 0; }堆的应用
堆排序
堆排序主要利用堆的思想进行排序。
步骤：
1.建堆（升序建大堆；降序建小堆）
2.利用堆删除的思想来排序。（这也解释了为什么升序要建大堆，因为大堆确定了最大素在堆顶）
向下调整建堆
从最后一个非叶子节点开始，向上遍历直到根节点，对每个节点进行调整，以确保其满足堆的性质。
步骤：
- 从最后一个非叶子节点开始，该节点的索引为
n/2 - 1，其中n是数组的长度。 - 对每个节点，检查其子节点，如果存在违反堆性质的情况（在最大堆中，子节点大于父节点；在最小堆中，子节点小于父节点），则交换父节点和较大的子节点。
- 继续这个过程，直到节点满足堆性质或到达根节点。
void AdjustDown(int* arr, int size, int parent) { int child = 2 * parent + 1; while (child < size) { //假设法找出左右孩子中大的那个节点 if (child + 1 < size && arr[child] < arr[child + 1]) { child++; } if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child; child = 2 * parent + 1; } else { break; } } }- 时间复杂度O(n)
向上调整建堆
从第一个内部节点开始，向下遍历直到根节点，对每个节点进行调整。这种方法从底部开始，逐步向上调整节点。
步骤：
- 从第一个内部节点开始，该节点的索引为
n/2，其中n是数组的长度。 - 对每个节点，检查其父节点，如果当前节点违反了堆性质（在最大堆中，当前节点大于父节点；在最小堆中，当前节点小于父节点），则交换它们。
- 将交换后的节点视为新的当前节点，重复上述过程，直到当前节点满足堆性质或到达根节点。
void AdjustUp(HPDataType* arr, int child) { assert(arr); int parent = (child - 1) / 2; while(child > 0)// parent >= 0 是错的 parent = (0 - 1) / 2 == 0 { if (arr[child] > arr[parent]) { //交换 Swap(&arr[child], &arr[parent]); child = parent; parent = (child - 1) / 2; } else { break;; } } }- 时间复杂度O(nlogn)
对比两种建堆方式，我们应当使用向下调整建堆。
利用堆删除来排序
当数组建堆建好后，交换堆顶素和最后一个素，缩小堆的范围，向下重新调整堆，重复此过程，直到堆的大小为1，说明数组已经排序好了。
void Swap(int* p1, int* p2) { int tep = *p1; *p1 = *p2; *p2 = tep; } void AdjustDown(int* arr, int size, int parent) { int child = 2 * parent + 1; while (child < size) { //假设法找出左右孩子中大的那个节点 if (child + 1 < size && arr[child] < arr[child + 1]) { child++; } if (arr[child] > arr[parent]) { Swap(&arr[child], &arr[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } void HeapSort(int* arr, int size) { //向下建堆 //升序 建大堆 //降序 建小堆 for (int i = (size - 2) / 2; i >= 0; i--) { AdjustDown(arr, size, i);//大堆 } int end = size - 1; while (end >= 0) { Swap(&arr[end], &arr[0]); AdjustDown(arr, end, 0); end--; } }堆排序的总时间复杂度是 O(n)（构建堆）+ O(nlogn)（堆排序过程），结果是 O(nlogn)。
- 时间复杂度：最好最坏都是O(nlogn)
- 空间复杂度：O(1)
拜拜，下期再见😏
摸鱼ing😴✨🎞
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/96339.html