当前位置：首页 > news >正文

堆的应用（堆排序，TOP-K问题）详细讲解

news 来源：原创 2024/4/29 9:26:05

在这里插入图片描述
所有人都关心我飞的高不高，只有我妈关心我翅膀硬不硬

一、堆的应用

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，数组中的元素便以排好顺序。

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);
}