呀哈喽,我是结衣
前言
今天给大家带来的堆排序的topk问题。topk就是在许多数中,找出前k个大的数,可能是几十个数,也可能是几千万个数中找。今天我们将要在1000000(一百万)个数中找出前10大的数。
知识点
C语言文件的读写
建堆
向下调整排序
随机数的产生
ps 向下调整和向上调整的教学都在我的另一篇文章堆的实现当中,不懂的小伙伴可以先学习堆的实现
文件的创建
随机数的生成
生成随机数我们要用到rand函数,但是因为rand函数生成随机数需要种子,所以我要还要用到srand函数为其生成种子
但问题又来了,随机种子哪来的,难道在用rand吗?这显然就不行了,那么time函数就要被我们利用了,time会根据时间的变化而该,所以我们就用time来生成随机种子。
srand(time(0));
time函数的头文件为<time.h>,srand和rand都为<stdlib.h>.
文件的写入
我们要在一百万个数中找前10大的数肯定不能直接把一百万个数打印在屏幕里吧,所以我们要把这一百万个数存放在文件data.txt中。
写入文件要用到fopen
void Createnode()
{
int n = 1000000;
srand(time(0));
char file[] = "data.txt";
FILE* fin = fopen(file, "w");//只写方式
if (fin == NULL)//"w"表示只写的意思,if语句为了防止文件创建失败
{
perror("file error\n");
return;
}
for (int i = 0; i < n; i++)
{
int x = rand()+i % 1000000;//rand只能产生3万个随机数,所以我们加个i
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
看看效果吧。
在记事本里生成了一百万个数,大约8mb。
topk的实现
文件的读取
文件的读取非常简单把w改为r就可以了
FILE* fin = fopen(file, "r");//只读方式
if (fin == NULL)
{
perror("file error\n");
return;
}
topk思路
我们要把一百万个数里前k个的大数找出来,是建小堆还是建大堆。
给大家3秒钟的时间思考:
3
2
1
那么答案是建小堆,为什么呢?小堆就是小的数据在上,大的数据在下。我们先建一个可以储存k个数据的小堆,把文件里前k个的数先存入小堆中,如果在遍历这一百个万个数,只要比堆顶的数据大就把它插入堆顶,然后先下调整,循环往复这个堆里就会挤满一百万数中前k大的数了。利用的就是小堆中大的数都在下面不会堵住里堆顶,以至于后面的数进不来。
建立小堆
我们假设k为10,就是说找前10大的数,那么我们就要建立一个空间为10的小堆:
int* a = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; i++)
{
fscanf(fin, "%d", &a[i]);//将文件中的数写入数组当中
adjustup(a, i);//向上调整,建立小堆。
}
向上调整
void adjustup(HpDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child>0)
{
if (a[child] < a[parent])
{
swap(a,child, parent);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
遍历文件
在这里我们要了解,写入数据到文件中时会在最后加入一个EOF,所以只要我们读到EOF就退出循环,
int x = 0;
while (fscanf(fin, "%d", &x) != EOF)
{
if (x > a[0])
{
a[0] = x;
adjustdown(a, 0, k);
}
}
在遍历当中我们把比堆顶大的数替换原来的堆顶,然后向下调整,形成新的小堆。
向下调整
void adjustdown(HpDataType* a, int parent, int size)
{
int child = parent * 2 + 1;
if (a[child] > a[child + 1])
{
child++;
}
while (child < size)
{
//if (child+1<size && a[child] > a[child + 1])//inpustion
//{
// child++;
//}
if (a[parent] > a[child])
{
swap(a, child, parent);
parent = child;
child = parent * 2 + 1;
if (child+1<size&&a[child] > a[child + 1])//inpustion
{
child++;
}
}
else
{
break;
}
}
}
交换函数
void swap(HpDataType*a,int child, int parent)
{
HpDataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
}
完整代码
void Createnode()
{
int n = 1000000;
srand(time(0));
char file[] = "data.txt";
FILE* fin = fopen(file, "w");//只写方式
if (fin == NULL)
{
perror("file error\n");
return;
}
for (int i = 0; i < n; i++)
{
int x = (rand()+i) % 1000000;//rand只能产生3万个随机数。
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void PrintTopK(FILE* file,int k)
{
FILE* fin = fopen(file, "r");//只读方式
if (fin == NULL)
{
perror("file error\n");
return;
}
int* a = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; i++)
{
fscanf(fin, "%d", &a[i]);
adjustup(a, i);
}
for (int i = 0; i < k; i++)
{
printf("%d ", a[i]);
}
printf("\n");
int x = 0;
while (fscanf(fin, "%d", &x) != EOF)
{
if (x > a[0])
{
a[0] = x;
adjustdown(a, 0, k);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", a[i]);
}
fclose(fin);
}
int main()
{
Createnode();
int k = 0;
scanf("%d", &k);
PrintTopK("data.txt", k);
return 0;
}
运行效果
第二行为文件前10个数据小堆数据
当然最后你也可能会问,万一不是呢?这可是一百万个数啊,就算它随便打印,你也不知道是不是对的吧。emmm,你说的对,但是忍心让我用人力在这一百万个数据里面找吗。开玩笑啦,我当然有办法了,无奖竞猜,你会怎么办呢?
方法就是,我们来改数据,我们在文件里随机改几个数据让它一定会大于其他的数据,然后我们在看它有没有被打印出来。
ok,我现在偷偷改10个数据。我改里5个数,随机改的再让我们看看打印结果吧。
文章来源:https://www.toymoban.com/news/detail-766676.html
我不小心又运行了Createnode();导致里面的数字重新打印了,所以第二行和上面不一样
大家看看是不是把我们刚刚改的数都打印上去了,这就是topk问题。
完
文章来源地址https://www.toymoban.com/news/detail-766676.html
到了这里,关于数据结构——堆排序的topk问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!