本文主要是介绍【数据结构】堆的TopK问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
大家好,我是苏貝,本篇博客带大家了解堆的TopK问题,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️
目录
- 一. 前言
- 二. TopK
- 三. 代码
一. 前言
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决
二. TopK
思路:
- 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆 - 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
下面我们用找出1000000个元素中最大的5个值举例
1
为1000000个元素赋值
1000000个元素当然不可能是由我们手动赋值,我们想到有srand函数搭配time函数可以生成随机值。
以写的形式打开文件"data.txt",如果文件不存在,就会建立该文件。
我们知道,srand(time(0))能生成的随机值只有3万多个,这就意味着如果我们只用随机数赋值的话,会有将近997万的数据是重复的,所以我们在随机数的基础上再加一个会变的数,这样重复的数字就会比较少。
最后,将随机数写入文件中。
void CreateData()
{FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");return;}int n = 1000000;srand(time(0));for (int i = 0; i < n; i++){int x = 0;x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
在上面代码的操作下,我们能保证所有的随机值都<1000000,那我们如何确保最后的结果是正确的呢?我们可以在执行完这个函数后,再打开文件,随意修改5个值,让它们都>1000000,这样最后的值只能是我们修改了的。
注意:
在修改完5个值后,将调用main函数中调用CreateData函数的代码注释掉,否则再次运行程序,文件里的数据会重新被修改
2
如何建小堆?
1.先定义一个指针指向k个元素的数组
2.将文件的前k个元素边插入,边向上调整,最后得到小堆
了解fscanf
//void swap(int* a, int* b)
//{
// int tmp = *a;
// *a = *b;
// *b = tmp;
//}//void AdjustUp(int* a, int child)
//{
// assert(a);
//
// 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;
// }
//}FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail");return;}//1.建有k个元素的小堆int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("fopen fail");return;}//2.将前k个元素插入小堆中for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);AdjustUp(minheap, i);}
3
要找出最大的k个值时,为什么不用大堆?
因为如果最大值先出来,就占据了堆顶的位置,此时次大值就因为<最大值而不能进入大堆中。
4
得到TopK
用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素,再将新的堆顶元素向下调整
//void AdjustDown(int* a, int size, int parent)
//{
// assert(a);
//
// int child = parent * 2 + 1;
// while (child < size)
// {
// if (child + 1 < size && a[child + 1] < a[child])
// {
// child++;
// }
// if (a[child] < a[parent])
// {
// swap(&a[child], &a[parent]);
// parent = child;
// child = parent * 2 + 1;
// }
// else
// {
// break;
// }
// }
//
//}//3.遍历,如果有数比堆顶元素大的话,让堆顶元素=该元素,再向下调整while (fscanf(fout, "r") != EOF){int x = 0;fscanf(fout, "%d", &x);if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}
三. 代码
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<time.h>//构建数据
void CreateData()
{FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");return;}int n = 1000000;srand(time(0));for (int i = 0; i < n; i++){int x = 0;x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void AdjustUp(int* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}void AdjustDown(int* a, int size, int parent)
{assert(a);int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void PrintTopK(FILE* file, int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail");return;}//1.建有k个元素的小堆int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("fopen fail");return;}//2.将前k个元素插入小堆中for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);AdjustUp(minheap, i);}//3.遍历,如果有数比堆顶元素大的话,让堆顶元素=该元素,再向下调整while (fscanf(fout, "r") != EOF){int x = 0;fscanf(fout, "%d", &x);if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}free(minheap);fclose(fout);
}//TopK 找出最大的k个值
int main()
{//CreateData();PrintTopK("data.txt", 5);return 0;
}
好了,那么本篇博客就到此结束了,如果你觉得本篇博客对你有些帮助,可以给个大大的赞👍吗,感谢看到这里,我们下篇博客见❤️
这篇关于【数据结构】堆的TopK问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!