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

[C/C++]用堆实现TopK算法

一:引入

        思考一个问题:  怎么在100个数中找到前10个最大的数?

way1: 相信大多数人想到的方法是先把100个数放到数组中从大到小排序,再打印前10个数

way2: 前一文中我们讲了堆结构,那么就可以把这100个数建为大堆,再依次pop10次

        这种方法虽然再这个问题下可行,但是如果是再1亿个数中找最大的十个数呢?

当数据多到内存都放不下时这种方法显然不可取

二:TopK问题

        TopK问题就是说在N个数据中找到前k个最大或最小的数(前提是N远大于k)

解决方法:

        我们以找到前k个最大的数为例

  1. 将数据前k个数建成一个小堆
  2. 从第k+1个元素开始遍历数据,如果比堆顶元素大的话就交换
  3. 交换完以后,将堆顶元素向下调整到合适位置
  4. 依次反复遍历所有元素即可

为什么要建立小堆而不建大堆呢?

        因为如果建大堆,如果数据中最大的元素堵在堆顶,那剩下的k-1大的元素就进不了堆了,相反如果建立小堆,大的数据会往下沉,堆顶的元素是堆里面最小的元素,只要后面的数据比堆顶大就可以交换入堆,这样遍历完一遍数据后,最大的k个数就全部在堆里面了

模拟验证:

        在文件中创建10万个随机数,找前10个最大的数

1.先创建随机数

        由于rand创建的随机数只有三万多个,而我们需要10万个,这样就会有许多重复的数据,加i是为了让重复的数据减少,取模100000是为了将随机数控制在100000以内

void creatnum()
{srand(time(0));int n = 100000;FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen");return;}for (int i = 0; i < n; i++){int x = (rand() + i) % 100000;   //由于rand最多只能产生三万多个随机数,加i可以让重复的数字大幅减小fprintf(fin,"%d\n",x);}fclose(fin);
}

2.打印前5个最大的数据(TopK问题精髓) 重点重点!!

 对于向上调整法和向下调整法,可以看[C/C++]数据结构 堆的详解

void printTopk(const char* file,int k)
{FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen");return;}//创建一个小堆(找最大数创小堆,找最小数创大堆)int* heap = (HeapDataType*)malloc(sizeof(HeapDataType) * k);if (heap == NULL){perror("malloc");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &heap[i]);AdjustUp(heap, i);}//读数据,如果比堆头的数大就交换,再向下调整int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x > heap[0]){heap[0] = x;AdjustDown(heap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", heap[i]);}printf("\n");free(heap);fclose(fout);
}

3.测试代码

int main()
{creatnum();//printTopk("data.txt", 5);return 0;
}

        由于10万个数都是随机产生的,所以我们无法验证打印的数是不是正确的,但是我们直到这十万个数都是小于100000的,所以我们先调用创建随机数的函数,然后我们在打开文件,改五个大于100000的数,看打印结果是不是我们改的数即可.

ps:在修改完数据后,准备打印数据之前,一定要把创建随机数的函数注释掉,因为再次调用的话,我们是以'w'的方式打开文件的,如果文件存在的话数据会被清空重新产升随机数,这样我们改的数据就不存在了

相关文章:

[C/C++]用堆实现TopK算法

一:引入 思考一个问题: 怎么在100个数中找到前10个最大的数? way1: 相信大多数人想到的方法是先把100个数放到数组中从大到小排序,再打印前10个数 way2: 前一文中我们讲了堆结构,那么就可以把这100个数建为大堆,再依次pop10次 这种方法虽然再这个问题下可行,但是如果是再1亿…...

3D点云目标检测:VoxelNex解读(带源码/未完)

VoxelNext 通用vsVoxelNext一、3D稀疏卷积模块1.1、额外的两次下采样1.2、稀疏体素删减 二、高度压缩三、稀疏池化四、head五、waymo数据集训练六、训练自己的数据集bug修改 通用vsVoxelNext 一、3D稀疏卷积模块 1.1、额外的两次下采样 使用通用的3D sparse conv&#xff0c;…...

【Docker】从零开始:11.Harbor搭建企业镜像仓库

【Docker】从零开始&#xff1a;11.Harbor搭建企业镜像仓库 1. Harbor介绍2. 软硬件要求(1). 硬件要求(2). 软件要求 3.Harbor优势4.Harbor的误区5.Harbor的几种安装方式6.在线安装(1).安装composer(2).配置内核参数,开启路由转发(3).下载安装包并解压(4).创建并修改配置文件(5…...

使用conan包 - 工作流程

使用conan包 - 工作流程 主目录 conan Using packages1 Single configuration2 Multi configuration 本文是基于对conan官方文档Workflows的翻译而来&#xff0c; 更详细的信息可以去查阅conan官方文档。 This section shows how to setup your project and manage dependenci…...

【LeeCode】59.螺旋矩阵II

给定一个正整数 n&#xff0c;生成一个包含 1 到 n^2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 解&#xff1a; class Solution {public int[][] generateMatrix(int n) {int[][] ar…...

rsyslog学习

rsyslog是什么 RSYSLOG&#xff08;Remote System Logging&#xff09;是一个开源的日志处理工具&#xff0c;用于在 Linux 和 Unix 系统上收集、处理和转发日志。它是一个健壮且高性能的日志处理程序&#xff0c;可以替换 Syslogd 作为标准的系统日志程序。RSYSLOG 提供了许多…...

Navicat 技术指引 | GaussDB服务器对象的创建/设计(编辑)

Navicat Premium&#xff08;16.2.8 Windows版或以上&#xff09; 已支持对GaussDB 主备版的管理和开发功能。它不仅具备轻松、便捷的可视化数据查看和编辑功能&#xff0c;还提供强大的高阶功能&#xff08;如模型、结构同步、协同合作、数据迁移等&#xff09;&#xff0c;这…...

有哪些可信的SSL证书颁发机构?

目前市面上所显示的SSL证书颁发机构可所谓不计其数&#xff0c;类型也是多样&#xff0c;就好比我们同样是买一件T恤&#xff0c;却有百家不同类型的店铺一个道理。根据CA里面看似很多&#xff0c;但能拿到99%浏览器及设备信任度的寥寥无几&#xff0c;下面小编整理出几家靠谱可…...

MidJourney笔记(4)-settings

前面已经大概介绍了MidJourney的基础知识,后面我主要是基于实操来分享自己的笔记。可能内容顺序会有点乱,请大家理解。 这次主要是想讲讲settings这个命令。我们只需在控制台输入/settings,然后回车,就可以执行这个命令。 (2023年11月26日版本界面) 可能有些朋友出来的界…...

前端开发学习 (三) 列表功能

一、列表功能 1、列表功能 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><meta http-equiv"X-UA-Compa…...

win11渗透武器库,囊括所有渗透工具

开箱即用&#xff0c;最全的武器库&#xff0c;且都是2023年11月最新版&#xff0c;后续自己还可以再添加&#xff0c;下载地址&#xff1a;https://download.csdn.net/download/weixin_59679023/88565739 服务连接 信息收集工具 端口扫描 代理抓包 漏洞扫描 指纹识别 webshel…...

13-21-普通数组、矩阵

LeetCode 热题 100 文章目录 LeetCode 热题 100普通数组13. 中等-最大子数组和14. 中等-合并区间15. 中等-轮转数组16. 中等-除自身以外数组的乘积17. 困难-缺失的第一个正数 矩阵18. 中等-矩阵置零19. 中等-螺旋矩阵20. 中等-旋转图像21. 中等-搜索二维矩阵II 本文存储我刷题的…...

代码随想录算法训练营第四十六天【动态规划part08】 | 139.单词拆分、背包总结

139.单词拆分 题目链接&#xff1a; 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 求解思路&#xff1a; 单词是物品&#xff0c;字符串s是背包&#xff0c;单词能否组成字符串s&#xff0c;就是问物品能不能把背包装满。 动规五部曲 确定dp数…...

go语言基础 break和contine区别

背景 break和continue是编程语言的标准语法&#xff0c;几乎在所有的语言都有类似的用法。 go语言及所有其他编程语言for循环或者其他循环 区别 for i : 0; i < 10; i {if i 5 {continue}fmt.Println(i)for j : 0; j < 3; j {fmt.Println(strconv.Itoa(j) "a&q…...

vue3父子组件通过$parent与ref通信

父组件 <template><div><h1>ref与$parents父子组件通信 {{ parentMoney }}</h1><button click"handler">点击我子组件的值会减20</button><hr><child ref"children"></child></div> </te…...

PHP中的常见的超全局变量

PHP是一种广泛使用的服务器端脚本语言&#xff0c;它被用于开发各种Web应用程序。在PHP中&#xff0c;有一些特殊的全局变量&#xff0c;被称为超全局变量。超全局变量在整个脚本中都是可用的&#xff0c;无需使用global关键字来访问它们。在本文中&#xff0c;我们将深入了解P…...

leetcode9.回文数

回文数 0.题目1.WJQ的思路2.实现过程2.0 原始值怎么一个个取出来&#xff1f;2.1 取出来的数如何存到新的数字后面&#xff1f;2.2完整的反转得到新数的过程 3.完整的代码4.可运行的代码5.算法还可以优化的部分 0.题目 给你一个整数 x &#xff0c;如果 x 是一个回文整数&…...

springboot(ssm大学生二手电子产品交易平台 跳蚤市场系统Java(codeLW)

springboot(ssm大学生二手电子产品交易平台 跳蚤市场系统Java(code&LW) 开发语言&#xff1a;Java 框架&#xff1a;ssm/springboot vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&#xff1a;mysql 5.7&#xff08;或…...

关于微信小程序中如何实现数据可视化-echarts动态渲染

移动端设备中&#xff0c;难免会涉及到数据的可视化展示、数据统计等等&#xff0c;本篇主要讲解原生微信小程序中嵌入echarts并进行动态渲染&#xff0c;实现数据可视化功能。 基础使用 首先在GitHub上下载echarts包 地址&#xff1a;https://github.com/ecomfe/echarts-for…...

在Windows WSL (Linux的Windows子系统)上运行的Ubuntu如何更改主机名

在Windows 安装的Ubuntu&#xff0c;如何修改主机名。有列了两种方法&#xff0c;提供给大家参照。 文章目录 方法一&#xff1a;hostname指令修改方法二&#xff1a;修改配置文件修改hostnanmewsl.conf 文件配置选项推荐阅读 方法一&#xff1a;hostname指令修改 hostname指…...

百川2-13B量化模型提示工程:降低OpenClaw操作失误率

百川2-13B量化模型提示工程&#xff1a;降低OpenClaw操作失误率 1. 问题背景与挑战 去年冬天&#xff0c;当我第一次尝试用OpenClaw自动化整理电脑上积压的半年项目文档时&#xff0c;遭遇了令人崩溃的"AI灾难现场"——这个本该帮我分类归档的助手&#xff0c;把财…...

YOLOv11桌面应用实战:PyQt5打造智能监控与目标追踪系统

1. YOLOv11与PyQt5的强强联合 在计算机视觉领域&#xff0c;YOLO系列模型一直以其实时性和准确性著称。最新发布的YOLOv11在保持原有优势的基础上&#xff0c;进一步优化了模型结构和训练策略&#xff0c;使其在小目标检测和复杂场景下的表现更加出色。而PyQt5作为Python生态中…...

RK3568实战:用QEMU在x86电脑上模拟构建和调试ARM64 Ubuntu 22.04根文件系统

RK3568开发实战&#xff1a;基于QEMU的ARM64根文件系统高效构建与调试指南 引言 在嵌入式Linux开发领域&#xff0c;RK3568作为一款性能优异的四核Cortex-A55处理器&#xff0c;正被广泛应用于各类智能硬件设备。传统开发流程中&#xff0c;开发者往往需要在物理开发板上反复刷…...

RT-Thread信号量机制解析与应用实践

1. RT-Thread信号量机制深度解析在嵌入式实时操作系统中&#xff0c;线程同步是确保多线程有序协作的关键机制。RT-Thread作为一款优秀的实时操作系统&#xff0c;提供了包括信号量在内的多种同步方式。信号量特别适合处理资源计数和线程间同步的场景&#xff0c;比如传感器数据…...

从修车铺到世界冠军,从废塑料到再生资源:一场关于坚持与价值的时代对话

最近&#xff0c;张雪的故事刷屏了。这个14岁辍学、睡在修车铺阁楼、月薪300元的湖南山村少年&#xff0c;用了整整二十年&#xff0c;将自己亲手打造的摩托车送上了世界超级摩托车锦标赛&#xff08;WSBK&#xff09;的冠军领奖台。当五星红旗在葡萄牙阿尔加维国际赛道升起时&…...

OpenClaw创意辅助:Qwen3.5-9B-AWQ-4bit实现设计草图转文案

OpenClaw创意辅助&#xff1a;Qwen3.5-9B-AWQ-4bit实现设计草图转文案 1. 为什么设计师需要AI创意辅助 作为独立设计师&#xff0c;我经常遇到这样的困境&#xff1a;在灵感迸发时快速绘制的手稿&#xff0c;几天后回看却难以还原当时的完整思路。传统工作流中&#xff0c;我…...

嵌入式与单片机:核心概念与开发实战解析

1. 嵌入式与单片机&#xff1a;从概念到实战的全面解析作为一名在嵌入式领域摸爬滚打多年的工程师&#xff0c;我经常被问到这样一个问题&#xff1a;"单片机不就是嵌入式吗&#xff1f;"这个问题看似简单&#xff0c;却反映了初学者对这两个概念的普遍困惑。今天&am…...

嵌入式系统引导程序uboot原理与应用详解

1. 为什么嵌入式系统需要uboot1.1 计算机系统启动的基本原理任何计算机系统启动时都需要一个引导程序来完成硬件初始化和操作系统加载的工作。无论是PC机还是嵌入式设备&#xff0c;这个基本原理都是相通的。在PC架构中&#xff0c;这个引导程序叫做BIOS&#xff08;基本输入输…...

2025届毕业生推荐的五大降AI率方案解析与推荐

Ai论文网站排名&#xff08;开题报告、文献综述、降aigc率、降重综合对比&#xff09; TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 人工智能写作工具&#xff0c;是借助自然语言处理以及深度学习技术制造的智能辅助系统&#…...

2007 Text 3

2007 Text 3...