所有人都关心我飞的高不高，只有我妈关心我翅膀硬不硬
一、堆的应用
1. 堆排序
1.1 建堆
1.2 利用堆删除思想来进行排序
2.TOP-K问题
二、完结撒❀
–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–
学习一个知识，我们起码要直到它的用途，那样才算学会了
一、堆的应用
1.堆排序
大家肯定都学过冒泡排序，快速排序等等，在学完堆之后我们也可以用堆来实现数据排序。
（ps：冒泡排序的时间复杂度：O（N^2））
1.1 建堆
升序：建大堆
降序：建小堆
建堆方式可能与大家预想的不太一样，但确实如此，升序我们需要建大堆，降序我们建小堆，再利用堆删除的思想进行排序，时间复杂度会低很多。
1.2 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序
代码实现：
void Swap(HPDataType* px, HPDataType* py)
{
HPDataType tmp = *px;
*px = *py;
*py = tmp;
}
//向下调整O(logN)
void AdJustDown(HPDataType* a, int n, int parent)
{
//从左孩子开始,child为小孩子那个
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child] > a[child + 1])
{
++child;
}
if (a[child] < a[parent])//小堆<,大堆>
{
Swap(&a[parent], &a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}
//升序 大堆 O(N*logN)
//降序 小堆 O(N*logN)
void HeapSort(HPDataType* a, int n)
{
//根据数组直接建堆 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdJustDown(a, n, i);
}
//交换根和尾的位置，再向下对前end（end每次少一个）的数进行调整 O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdJustDown(a, end, 0);
--end;
}
}
只需要将要排序的数组地址和数组元素的总个数作为实参传过来，并且会向下调整，就可以实现排序。
这样的堆排序时间复杂赋为O（N*logN）
我们拿一个数组以降序排小堆为大家举例讲解：
int arr[] = {5,2,3,6,1,4,7}
逻辑图解：
因为每次向下调整，根一定是数组中最小值，将最小值与当前数组访问的尾坐标进行交换，直到end为0，数组中的元素便以排好顺序。
堆排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.TOP-K问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
为了更好的给大家讲解，我们可以现根据文件操作手动造出一些数据来
代码如下：
//造数据
void CreateNDate()
{
int n = 10000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = rand();
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
以读的方式在data.txt文件中造出10000个随机数
效果如下：
当然，如果感觉10000个数据不够多，可以手动添加更多数据。
接下来我们就在这10000个数据中进行TOp-K问题的讲解
如何在这10000个数据中选出前K个最大的数呢？
上面对TOP-K问题的讲解已经给出了思路
我们可以先看一下代码实现：
//按照大小选出前k个值
void Tokp()
{
//选出前k个最大数据
printf("请输入前几个最大的值:>");
int k = 0;
scanf("%d", &k);
//将数据中前k个数据存入到创建的minheap数组中
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc fail");
return;
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
}
//建堆(向下建堆)
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdJustDown(minheap, k, i);
}
//判断大小进行替换
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
if (minheap[0] < x)
{
minheap[0] = x;
AdJustDown(minheap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
fclose(fout);
}
这里对文件操作函数比如：fscanf，fprintf等不太熟悉的同学建议去官网进行查询如何使用之后再进行Top-K问题的学习
官网网址：cplusplus
假设我们要前10个最大的数据，那么输入k为10.
实现逻辑步骤：
1.输入k为10
2.以读的方式打开data.txt文件
3.创建一个10个数据空间大小（单位为字节）的数组
4.将文件中前10个数存入到数组中
5.对数组进行向下建堆（这里我们要前10个最大的数据，所以要建小堆）
6.将根节点以此与剩余9990个数据进行对比，大于根节点就进行替换再对前十个数据进行向下调整
7.打印数组，关闭文件
因为创建的是小堆，那么根节点的值一定是堆中最小的，如果后续数据大于根节点的值，替换后再向下调整，最后对比完数据前十个建好的小堆数据就是这10000个数据中最大的10个。
调用函数打印结果：
因为10000个数据比较大，并且我们也并不知道这10000个数据中都有哪些数组，心里没有底
那么会不会有同学怀疑打印出的数值是否正确呢？
下面我教大家怎么检验所敲的该函数是否正确
我们可以在造数据的函数中做一些手脚
代码如下：
//造数据
void CreateNDate()
{
int n = 100000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = (rand()+i)%10000;//检验程序准确
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
这次我们将造出来的随机数该成100000个（判断数据增多会不会出现BUG）
再将造出来的每一个随机数都加上i并且余上10000
因为随机数所返回的数值大小范围为30000左右，我们为了让造出来的数更加随机，就每次加上i
余上10000的目的是为了让造出来的数字都在0~9999之间
之后我们直接执行该函数
执行后打开data.txt文件夹，我们会看到100000个数值在0~9999之间的数组
我们在该文件夹中随机更改5个数字，将这5个数字都改成大于10000的值，越大越好，之后保存
再对该文件里的所有数值进行Tokp，假设输入k为10，那么最后出来结构只要包含我们所更改的5个数据，就说明该函数打印前k个最大数据是正确的。文章来源：https://www.toymoban.com/news/detail-845978.html
二、完结撒❀
如果以上内容对你有帮助不妨点赞支持一下，以后还会分享更多编程知识，我们一起进步。
最后我想讲的是，据说点赞的都能找到漂亮女朋友❤
文章来源地址https://www.toymoban.com/news/detail-845978.html
到了这里，关于数据结构进阶篇 之 【堆的应用】（堆排序，TOP-K问题）详细讲解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
