数据结构——堆的应用 Topk问题

2024-03-10 15:36

本文主要是介绍数据结构——堆的应用 Topk问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

💞💞 前言

hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹
在这里插入图片描述

💥个人主页:大耳朵土土垚的博客
💥 所属专栏:数据结构学习笔记 、C语言系列函数实现
💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写在评论区或者私信我哦~

🥳🥳前面我们学习了利用堆进行排序,今天我们将继续介绍利用堆解决前k个最值的问题,Topk问题(在N个数中找出最大的前k个)在实际生活中也非常常见,💥💥比如店外卖时评分最高的前十家店铺,玩王者时英雄战力前十名等与排序排名有关的应用。

🥰🥰解题思路

正常思路 将这N个数建成一个大堆,然后Popk次,就可以找出最大的前k个 ;
💫💫但是如果N非常大以亿计(10亿个整数所占空间大概4G)那么就会非常耗时耗力,难以计算。

这里给出一种更好的解决办法:

①将前k个数建成小堆;(必须是小堆哦~)
②后面N-k个数依次比较,如果比堆顶的数据大,就替换它进堆
③然后将替换后的再向下调整使之重新成为一个小堆;
④最后这个小堆的值就是最大的前k个。

在写题之前我们先要创造N个数,可以通过c语言的文件操作以及随机生成函数来获得并写入文件中:

代码如下:

#include<time.h>
//创造N个数据
void CreatData()
{//造数据int n = 1000;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() % 10000;fprintf(fin, "%d\n", x);}fclose(fin);
}

✨✨这里使用了srand生成随机数需要包含time.h头文件;
int x = rand() % 10000;这个式子可以帮助我们生成10000以内的随机数;
fprintf可以帮助我们将生成的随机数写入到文件中(如下图生成了data文件):

在这里插入图片描述

所以生成文件后为了找到最大的前k个,我们可以手动改一些数据来验证后续代码的正确性:

在这里插入图片描述

这里手动改了5个,后面如果找出这五个最大的数就说明我们写的代码是正确的啦~🥳🥳
为了保证文件数据不被覆盖,我们在运行一次CreatData()函数之后就可以把它屏蔽掉了,此时已经生成了n个数据的文件data.txt了。


int main()
{//CreatData();//屏蔽PrintTopk(5, 1000);return 0;
}

Topk排序

造完数据后我们就可以利用之前学习过的堆来求出Topk啦

代码如下:

void PrintTopk(int k,int n)
{//打开文件const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}//创建顺序表开辟空间int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}//从文件中读取k个数for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]);}//将读取的k个数创建为小堆//堆向下调整算法for (int i = (k - 2) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}//将剩余N-k个数依次与堆顶元素比较for (int i = 0; i < n - k; i++){int tmp = 0;fscanf(fout, "%d", &tmp);if (tmp > kminheap[0]){Swap(&tmp, &kminheap[0]);AdjustDown(kminheap, k, 0);}}//打印前k个元素for (int i = 0; i < k; i++){printf("%d\n", kminheap[i]);}
}

对于造小堆以及排序有疑问的可以看看土土的上篇博客🥰🥰——堆排序详解

运行代码如下:

int main()
{//CreatData();PrintTopk(5, 1000);return 0;
}

运行结果如下:
在这里插入图片描述

🎉🎉完全正确~是我们之前改的那五个数,说明我们的代码将它从1000个数中找了出来🥳🥳至此Topk问题得到解决 ~

✨✨这里再提一句,打印出来的虽然是n个数中的最大的k个但是我们发现打印的顺序是乱的,通过之前排序的学习,大家知道怎么将他们按顺序打印出来吗?有兴趣的小伙伴可以尝试一下~🥳🥳

结语

以上就是数据结构中利用堆排序求解Topk问题啦,关键在于对于堆排序的理解与运用~有疑问的小伙伴可以将问题打在评论区或者私信我哦 ~完结撒花 ~🥳🥳🎉🎉🎉

这篇关于数据结构——堆的应用 Topk问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/794693

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash?1.1

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使