堆排序-调整算法
个人主页点这里!~
1.堆
了解堆排序首先要了解一下堆这个数据结构
堆（Heap）是一种特殊的树形数据结构，它通常被表示为一个完全二叉树或近似完全二叉树，并且满足堆性质（Heap Property）。堆主要分为两种：大堆（Max Heap）和小堆（Min Heap）。
我们有一个待排序数组{5,4,7,9,3,2,6,1},将他层序遍历为堆,如下图
在堆中,我们在做一个大堆时要保证大的元素始终在小的上面,做一个小堆时,要保证小的元素始终在大的上面,所以我们需要实现两种调整函数:
-
向上调整（adjustup）：
- 操作方向：从子节点向父节点移动数据。
- 目的：当在堆的底部插入一个新的元素时，或者当一个元素的值增加并可能破坏堆的性质时，需要向上调整来保持堆的性质。具体来说，如果一个节点的值大于其父节点的值（在最大堆中），或者小于其父节点的值（在最小堆中），那么这个节点就需要与其父节点交换位置，并且这个过程可能需要继续向上进行，直到堆的性质被恢复。
void AdjustUp(HPDataType* a, int child) {int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent])//СڽС{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}} }
-
向下调整（adjustdown）：
- 操作方向：从父节点向子节点移动数据。
- 目的：当从堆顶删除一个元素（通常是根节点），或者当一个元素的值减小并可能破坏堆的性质时，需要向下调整来保持堆的性质。具体来说，新的根节点（或从堆的末尾移到根节点的元素）可能与它的子节点之一或两个都不满足堆的性质，这时就需要将这个节点与其较大的子节点（在最大堆中）或较小的子节点（在最小堆中）交换位置，并且这个过程可能需要继续向下进行，直到堆的性质被恢复。
void AdjustDown(HPDataType* a, int n, int parent) {int child = parent * 2 + 1;while (child < n){if (a[child] > a[child + 1] && child + 1 < n){child++;}if (a[child] < a[parent])//СڽС{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}} }
2.堆排序(排升序)
我们如何利用堆这个结构实现排序呢?
第一步:建堆
-
那我们排升序是建大堆还是建小堆呢?
先说结论: 排升序建大堆,降序建小堆
我们先用反证法:我们排升序建一个小堆,看看会出现什么情况
我们排升序此时1,2,3,4,5位置已经正确了,但我们排剩下的数据时无法高效的排序,难道把剩下的数据拿出来再建堆,那消耗就太大了,并且节点之间关系全乱了,兄弟变父子,父亲变兄弟(我把你当兄弟,你却想当我爸爸)(比如7和6,本来是兄弟,再建堆就变成了兄弟)
所以我们不能建小堆,应该建大堆,那大堆的性质帮助我们如何解决你?看第二步
第二步:排序
我们建一个大堆
因为我们建一次大堆将最大的元素放到了堆顶
所以我们首先将堆顶的最大元素与最后一个元素交换位置,
然后把最大的元素踢出,因为在最后,所以堆不会产生向上面的问题
最后再建大堆,就找出第二大的元素在堆顶,如此往复
// 堆排序
void HeapSort(int* a, int n)
{
// 总结:升序建大堆
// 降序建小堆for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}
//2.向下调整排序int end = n - 1;while (end > 0)//一次循环把最小值排出(小堆的性质:小的永远在上面){Swap(&a[0], &a[end]);// 选出次小的--end;AdjustDown(a, end, 0);}
}
分享到这里 个人主页点这里!~