【C语言】Top K问题【建小堆】

前言

TopK问题:从n个数中,找出最大(或最小)的前k个数。

在我们生活中,经常会遇到TopK问题

比如外卖的必吃榜;成单的前K名;各种数据的最值筛选

问题分析

显然想开出40G的空间是不现实的,那应该怎么办呢?

答案是:建小堆

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<time.h>// 造数据
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() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void Swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}
//向下调整算法
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && 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(int k)
{FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen mail");return;}int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("minheap mail");return;}for (int i = 0; i < k; i++){fscanf_s(fout, "%d", &minheap[i]);}//建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minheap, k, i);}int x = 0;int val = 0;while (val = fscanf_s(fout, "%d", &x) != EOF){if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}fclose(fout);
}
int main()
{//CreateNDate();printf("请输入k:>");int k = 0;scanf_s("%d", &k);PrintTopK(k);return 0;
}

运行结果:

结果验证

那我们怎么确定输出在屏幕上的数据就是最大的数据呢?

我们可以在已经创建的数据上面修改,如图后面111的是在原有数据上手动添加的

重新运行,结果与预期一致

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/391304.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于STM32的温湿度监控系统

目录 引言环境准备工作 硬件准备软件安装与配置系统设计 系统架构硬件连接代码实现 初始化代码主循环代码应用场景 家居环境监控工业环境监控常见问题及解决方案 常见问题解决方案结论 1. 引言 在智能家居和工业自动化中&#xff0c;温湿度监控系统是一个非常重要的组成部分…

Java企业微信服务商代开发获取AccessToken示例

这里主要针对的是企业微信服务商代开发模式 文档地址 可以看到里面大致有三种token&#xff0c;一个是服务商的token&#xff0c;一个是企业授权token&#xff0c;还有一个是应用的token 这里面主要有下面几个参数 首先是服务商的 corpid 和 provider_secret &#xff0c;这个可…

使用GCC编译Notepad++的插件

Notepad的本体1是支持使用MSVC和GCC编译的2&#xff0c;但是Notepad插件的官方文档3里却只给出了MSVC的编译指南4。 网上也没有找到相关的讨论&#xff0c;所以我尝试在 Windows 上使用 MinGW&#xff0c;基于 GCC-8.1.0 的 posix-sjlj 线程版本5&#xff0c;研究一下怎么编译…

快手商业化 Java后端 二面|面试官很nice

面试总结&#xff1a;没有那种纯八股问题&#xff0c;都是偏向于情景题。看到面试官最后出了一道多叉树的题目&#xff0c;我以为是想直接刷人&#xff0c;但还是尽力去尝试了一下&#xff0c;最后也没做出来&#xff0c;面试官很nice&#xff0c;在答不上来的时候会引导我去思…

JVM—垃圾收集算法和HotSpot算法实现细节

参考资料&#xff1a;深入理解Java虚拟机&#xff1a;JVM高级特性与最佳实践&#xff08;第3版&#xff09;周志明 1、分代回收策略 分代的垃圾回收策略&#xff0c;是基于这样一个事实&#xff1a;不同的对象的生命周期是不一样的。因此&#xff0c;不同生命周期的对象可以采取…

python实现小游戏——植物大战僵尸(魔改版本)

制作一款DIY的‘植物大战僵尸’游戏引起了很多人的兴趣。在这里&#xff0c;我将分享一个使用Python语言在PyCharm环境中开发的初始状态版本。这个版本主要应用了pygame库来完成&#xff0c;是一个充满创意和趣味的魔改版本。 文章目录 前言一、开发环境准备二、代码1.main方法…

Linux小组件:gcc

gcc 是C语言的编译器&#xff0c;在Linux下我们也用这个编译C语言 安装gcc sudo apt install build-essential 查看gcc版本信息 gcc --version 有时候会出现代码编译不过去的问题&#xff0c;通常可能是gcc的编译标准太低&#xff0c;不支持某些写法 比如在很多旧的编译标…

SQL注入实例(sqli-labs/less-4)

0、初始页面 1、确定闭合符号 前两条判断是否为数值型注入&#xff0c;后两条判断字符型注入的闭合符号 ?id1 and 11 ?id1 and 12 ?id1" ?id1") 2、确定表的列数 ?id1") order by 3 -- 3、确定回显位置 ?id-1") union select 1,2,3 -- 4、爆库…

【kali靶机之serial】--反序列化漏洞实操

kali靶机配置 【我图片里没有截图的默认配置即可】需要改的地方图片里面都有。 使用kali扫描网关的主机。 扫到一个开放了80端口HTTP协议的主机ip 访问80端口 会看到一个文本页面&#xff0c;翻译一下看是什么意思。。 F12查看cookie&#xff0c;是一个base64编码了的东西 使…

新手小白学习PCB设计,立创EDA专业版

本教程有b站某UP主的视频观后感 视频链接&#xff1a;http://【【教程】零基础入门PCB设计-国一学长带你学立创EDA专业版 全程保姆级教学 中文字幕&#xff08;持续更新中&#xff09;】https://www.bilibili.com/video/BV1At421h7Ui?vd_sourcefedb10d2d09f5750366f83c1e0d4a…

指标一致化处理

什么是数据指标 数据指标有别于传统意义上的统计指标&#xff0c;它是通过对数据进行分析得到的一个汇总结果&#xff0c;是将业务单元精分和量化后的度量值&#xff0c;使得业务目标可描述、可度量、可拆解。 数据指标有哪些类型 极大型:期望取值越大越好&#xff1b; 极小…

Memcached未授权访问漏洞

Memcached 是一套常用的 key-value 分布式高速缓存系统&#xff0c;由于 Memcached 的安全设计缺陷没有权限控制模块&#xff0c;所以对公网开放的Memcache服务很容易被攻击者扫描发现&#xff0c;攻击者无需认证通过命令交互可直接读取 Memcached中的敏感信息。 app"Mem…

AI电销机器人的效果与作用

ai电销机器人的工作效率是非常高的&#xff0c;电销机器人一天的外呼量至少是3000左右&#xff0c;工作效率是人工的十倍还多&#xff0c;并且电销机器人没有负面情绪&#xff0c;一直都可以保持高昂的工作热情&#xff0c;非常简单方便。 并且ai电销机器人是越用越聪明的&…

英国AI大学排名

计算机学科英国Top10 “计算机科学与信息系统”学科除了最受关注的“计算机科学”专业&#xff0c;还包括了“人工智能”“软件工程”“计算机金融”等众多分支专业。 1.帝国理工学院 Imperial College London 单以计算机专业本科来讲&#xff0c;仅Computing这个专业&#x…

来点八股文(五) 分布式和一致性

Raft raft 会进入脑裂状态吗&#xff1f;描述下场景&#xff0c;怎么解决&#xff1f; 不会。raft通过选举安全性解决了这个问题&#xff1a; 一个任期内&#xff0c;follower 只会投票一次票&#xff0c;且先来先得&#xff1b;Candidate 存储的日志至少要和 follower 一样新…

用uniapp 及socket.io做一个简单聊天app 4

界面如下&#xff1a; <template><view class"container"><input v-model"username" placeholder"用户名" /><input v-model"password" type"password" placeholder"密码" /><butto…

comfyUI-MuseTalk的参数设置

comfyUI-MuseTalk的参数设置 目录 comfyUI-MuseTalk的参数设置 一、ComfyUI-VideoHelperSuite 二、comfyUI-MuseV合成的参考视频 2.1、什么时候会用到MuseV&#xff1f; 2.2、MuseV特别消耗系统内存 2.2.1、测试图片序列的像素比 2.2.2、影响运动范围和生成结果的参数 …

Yarn:一个快速、可靠且安全的JavaScript包管理工具

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;还请三连支持一波哇ヾ(&#xff20;^∇^&#xff20;)ノ&#xff09; 目录 一、Yarn简介 二、Yarn的安装 1. 使用npm安装Yarn 2. 在macOS上…

基于Springboot的个人博客系统

文章目录 介绍访问地址一、功能展示1.前台首页归档相册留言关于我登陆注册 2.后台管理系统登陆页面首页文章管理相册管理写博客访客统计 介绍 基于Java&#xff08;Springboot&#xff09;可以用做毕业设计的个人博客系统&#xff0c;包括网站前台和后台管理系统两部分。网站前…

C++中const关键字的用法

C语言和C中const的不同 首先我们需要区分一下C语言中的const和C中的const&#xff0c;C语言中的const修饰的变量可以不初始化&#xff0c;但如果将一个变量定位为const类型还不初始化&#xff0c;那么之后就不能对这个变量直接赋值了。 如果我们使用C语言中的const定义的变量指…