当前位置: 首页 > 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指…...

MAI-UI-8B应用案例:医疗登记表智能填充实战

MAI-UI-8B应用案例&#xff1a;医疗登记表智能填充实战 1. 医疗表单处理的痛点与解决方案 在医疗信息化系统中&#xff0c;患者登记表是每个医疗机构每天都要处理的基础文档。传统方式下&#xff0c;医护人员需要手动填写大量重复信息&#xff0c;不仅效率低下&#xff0c;还…...

Phi-4-mini-reasoning应用场景:技术文档自动逻辑校验与漏洞推理辅助工具

Phi-4-mini-reasoning应用场景&#xff1a;技术文档自动逻辑校验与漏洞推理辅助工具 1. 模型概述 Phi-4-mini-reasoning是一款由微软开发的3.8B参数轻量级开源模型&#xff0c;专为数学推理、逻辑推导和多步解题等强逻辑任务设计。该模型以"小参数、强推理、长上下文、低…...

Python 直驱打印机:从字体精调到标签排版,实战避坑指南

1. 为什么选择Python直驱打印机&#xff1f; 很多开发者第一次听说用Python直接控制打印机时都会觉得不可思议——毕竟我们习惯了通过Word、PDF等中间软件来打印文档。但当你需要批量生成标签贴、定制化报表或者自动化打印任务时&#xff0c;传统方式的弊端就暴露无遗&#xff…...

嵌入式 AI 助手的三层意图识别架构:如何在“快、准、稳“之间取得平衡

背景 我在开发一个项目协同平台的嵌入式 AI 助手。它不是独立的 chatbot&#xff0c;而是嵌在业务页面里的——用户可以在首页、项目详情页、任务抽屉等不同位置唤起它&#xff0c;用自然语言完成任务查询、创建、删除等操作。 和通用对话 AI 不同&#xff0c;这个助手有两个硬…...

台达 PLC ES 与 3 台欧姆龙 E5CC 温控器通讯程序分享

台达PLC ES与3台欧姆龙E5CC温控器通讯程序 程序带注释&#xff0c;并附送昆仑通态和威纶通触摸屏有接线方式&#xff0c;设置 程序温度可靠 器件&#xff1a;台达DVP ES系列的PLC&#xff0c;3台欧姆龙E5CC系列温控器&#xff0c;昆仑通态&#xff0c;威纶通触摸屏 功能&#x…...

Blender模型导入Unity材质丢失?5步搞定FBX材质完美迁移

Blender模型导入Unity材质丢失&#xff1f;5步搞定FBX材质完美迁移 当你花了数小时在Blender中精心雕琢模型材质&#xff0c;导出FBX到Unity后却发现材质全部丢失——这种崩溃感每个3D开发者都深有体会。材质丢失问题看似简单&#xff0c;实则涉及Blender与Unity两套完全不同的…...

【面板数据】地级市及区县人口空心化数据(2000-2024年)

人口空心化是指在城镇化和人口迁移过程中&#xff0c;区域青壮年劳动力及常住人口持续外流&#xff0c;导致人口规模收缩、人口老龄化加深、人口空间集聚能力下降和社会经济活力减弱的现象 参照陈义勇等&#xff08;2025&#xff09;文中关于人口空心化指标的衡量方式&#xf…...

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

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

告别卡顿:在Windows10上通过QEMU与WHPX硬件加速高效部署Ubuntu20.04开发环境

1. 为什么选择QEMUWHPX方案&#xff1f; 很多开发者都遇到过这样的困境&#xff1a;在Windows系统上运行Linux虚拟机时&#xff0c;要么性能拉胯到让人抓狂&#xff0c;要么配置复杂得让人望而却步。我之前用VMware跑Ubuntu时&#xff0c;光是开个浏览器就能让CPU飙到100%&…...

【技术干货】Qwen 3.6 Plus 实战:用百万上下文打造“代理式”AI 编码工作流

摘要 本文从工程视角拆解 Qwen 3.6 Plus&#xff1a;百万 token 上下文、面向“代理式编码”的能力&#xff0c;以及闭源旗舰开源工具的组合策略。结合实际项目需求&#xff0c;给出如何通过 OpenAI 兼容 API接入该类模型&#xff0c;并构建仓库级代码助手的完整 Python 示例和…...