前言
在讲堆的删除时，我们发现一步一步删除堆顶的数据，排列起来呈现出排序的规律，所以本节小编将带领大家进一步理解堆排序。
1.堆排序概念
那么什么是堆排序？
堆排序（Heap Sort）是一种基于堆数据结构的排序算法。它利用堆的性质（大堆或小堆）进行排序操作。堆排序的基本思想是通过构建堆，将待排序的数组转化为一个符合堆性质的堆结构，然后不断将堆顶元素与堆的最后一个元素进行交换，并调整堆，使剩余元素继续满足堆的性质。重复这个过程，直到整个数组有序。
堆排序的步骤如下：
- 构建大堆或小堆：将待排序的数组视为一个完全二叉树，通过从最后一个非叶子节点开始，依次对每个节点进行向下调整（Adjustdown）操作，构建出一个大堆或小堆。这个过程确保了堆的性质：对于大堆，父节点的值大于等于其子节点的值；对于小堆，父节点的值小于等于其子节点的值。
- 排序：交换堆顶元素（最大值或最小值）与堆的最后一个元素，并将堆的大小减一。然后对堆顶元素进行向下调整，使剩余元素继续满足堆的性质。重复这个过程，直到堆的大小为1，即所有元素都已经排好序。（运用堆删除的思想）
- 得到排序结果：经过上述步骤，数组中的元素就按照升序（从小到大）或降序（从大到小）排列了。
堆排序的时间复杂度为 O(nlogn)，其中 n 是待排序数组的大小。它具有原地排序的特点，不需要额外的存储空间。
堆排序的优点是稳定性较好，适用于大规模数据的排序。然而，堆排序的缺点是相对较慢，尤其在快速排序等其他排序算法的应用场景中，堆排序的性能可能不如其他算法。
2.堆的建立方法
2.1向下调整建立堆（补充）
在这里，堆的建立有两种，在二叉树的顺序结构中提到一种建堆的方法，通过尾插再进行向上调整，不过时间复杂度为O(N*logN),这里提供新的建堆方法，通过向下调整法，时间复杂度为O(N),不过再用此调整方法时，左右子树要是堆的结构。即从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点的树，就可以调整成堆。
假设给一个数组 int a[]={4,2,8,1,5,6,9,7,2,7,9},通过向下调整法制造大堆。
2.2向上调整法
通过比较新插入元素与其父节点的值来判断是否需要进行交换。如果新插入元素的值大于父节点的值，就将它们进行交换，并更新索引值。这样，逐步向上调整，直到新插入元素找到了合适的位置，保证了堆的性质。
//向上调整
void Adjustup(Datatype* 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;
}
}2.3建堆时间复杂度分析
1.向下调整法
void Adjustdown(Datatype* a, int n, int parent) {
//假设法,假设左孩子大
int child = parent * 2 + 1;
while (child < n ) {
if (child + 1 < n && a[child + 1] > a[child])
child = child + 1;
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else break;
}
}
2.向上调整法
向上调整法每层节点向上调整次数就是乘以层数
//向上调整
void Adjustup(Datatype* 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;
}
}
注意:上述代码都是采用建大堆的代码，建小堆把部分大于符号改成小于。
因此向下调整法实质上是节点数少的层,调整次数越多，向上调整是节点数越多，调整次数越多。
3.排序建堆选择
升序：建大堆
降序：建小堆
每次将堆首元素与尾元素交换，然后向下调整，每交换一次，堆的大小要减一，因为我们是每次将最大或者最小的元素依次交换堆后面。
例如升序的一个过程如下图：
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;
}
}
void TestHeap2()
{
int a[] = {20,17,16,5,3,4 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
printf("%d ", a[i]);
}
}4.TOP-K问题
TOP-K 问题：即求数据结合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大 。
比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。
对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决，基本思路如下：
若数据量小，可以直接建立相应的堆，在pop。
数据量很大的时候，可以采用以下方法：
1. 用数据集合中前 K 个元素来建堆
前k个最大的元素，则建小堆前k个最小的元素，则建大堆
2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。
假如求一堆数中的前k个最小的数，则建大堆。
这里我们采用随机数来生成100个随机数，然后存入一个动态数组中，然后选出前10个最小的数。
void PrintTopK(int* a, int n, int k)
{
// 1. 建堆--用a中前k个元素建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
Adjustdown(a, k, i);
}
// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
for (int j = n - k; j < n; j++) {
if (a[j] < a[0]) {
a[0] = a[j];
Adjustdown(a, k, 0);
}
}
printf("最小前%d个数:", k);
for (int i = 0; i < k; i++) {
printf("%d ", a[i]);
}
}
void TestTopk()
{
int n = 100;
int* a = (int*)malloc(sizeof(int) * n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 100;
}
PrintTopK(a, n, 10);
}本节内容到此结束，谢谢各位友友的捧场，下节小编将带领大家继续了解二叉树的链式存储结构！！！
留下三连和评论吧！！！
