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

【数据结构】（6.2）堆的应用——Top-K问题（C语言）

news 来源：原创 2024/7/9 2:20:44

系列文章目录

文章目录

系列文章目录
问题引入
一、TopK 问题是什么？
二、TopK 问题解决思路
- 2.1 TopK 思路
- 2.2 随机产生数字
- 2.2 完整代码
- 2.3 验证结果

问题引入

TopK 问题 (在一堆数据里面找到前 K 个最大 / 最小的数)。

一、TopK 问题是什么？

生活中也有很多实例，比如某外卖软件中有上千家店铺，我想选出当地好评最多的十家烤肉店，这时我们不用对所有数据进行排序，只需要取出前 K 个最大 / 最小数据。使用堆排序效率也更高。

二、TopK 问题解决思路

2.1 TopK 思路

思路一：将数组从小到大排序，拿到数组前3个元素。但是可以发现这样时间复杂度太高，不可取。

思路二：将元素全部放入一个堆结构中，然后弹出三个元素，每次弹出的元素都是当前堆最小的，那么弹出的三个元素就是前最小的三个元素。
这种思路可以做，但是假设我有1000000个元素，只弹出前三个最小的元素，那么就要用到大小为1000000的堆。这么做**空间复杂度太高，**不建议用这种方法。

【最佳方法】-- 方法三：最佳的方式就是用堆来解决，基本思路如下：

1、用数据集合中前 K 个元素来建堆。

前k个最大的元素，则建小堆
前k个最小的元素，则建大堆

2、用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素。将剩余 N-K 个元素依次与堆顶元素比完之后，堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。
————————————————

2.2 随机产生数字

//数据
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) % 10000000;fprintf(fin, "%d\n", x);}fclose(fin);
}

在这里插入图片描述

2.2 完整代码

向下调整法

		数据个数		要从哪里开始向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{//第一步找出最小的孩子(然后和父亲交换)//假设法 走边孩子最小int minchild = parent * 2 + 1;while (minchild < n)	//当没到最后一个{//左孩子和右孩子（谁最小呢？）//1.前提右孩子存在吧		2.右孩子小于小孩子if (minchild + 1 < n && a[minchild + 1] < a[minchild]){minchild++;		//最小孩子下标更新为右孩子}//开始调整if (a[minchild] < a[parent]){Swap(&a[minchild], &a[parent]);parent = minchild;minchild = parent * 2 + 1;}else{break;}}}

TOP-K核心代码

//TOP-K
void testHeap2()
{//N个数找最大的前K个//选最大的K个，先建一个前个K个数的小堆//打开FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen error");return;}	int k;printf("请输入k>:");scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}int i = 0;for (i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);		//读入前k个数}//建k个数的小堆for (i = (k - 1 - 1) / 2; i >= 0; i++){AdjustDown(kminheap,k,0);}//读取剩下的N-K个数int x = 0;while (fscanf(fout, "%d", &x)>0){if (x > kminheap[0])	//读入的元素大于堆顶元素{kminheap[0] = x;	//覆盖AdjustDown(kminheap,k,0);			//向下调整}}printf("最大前%d个数：", k);for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");}