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

【数据结构】建堆算法复杂度分析及TOP-K问题

【数据结构】建堆算法复杂度分析及TOP-K问题

🔥个人主页大白的编程日记

🔥专栏数据结构


文章目录

  • 【数据结构】建堆算法复杂度分析及TOP-K问题
    • 前言
    • 一.复杂度分析
      • 1.1向下建堆复杂度
      • 1.2向上建堆复杂度
      • 1.3堆排序复杂度
    • 二.TOP-K问题
      • 2.1思路分析
      • 2.2代码实现
    • 后言

前言

哈喽,各位小伙伴大家好!上期我们讲了堆排序和建堆算法。今天我们就来分析一下他们的时间复杂度。话不多说,咱们进入正题。向大厂冲锋!

一.复杂度分析

我们都知道堆是一个完全二叉树。那他的高度h和节点数量N有什么关系呢?

那我们再来对比一下满二叉树和完全二叉树的高度h.

我们用大O渐进表示法看的话他们两个的高度h都可以认为是logN的量级
所以我们的堆的上下调整可以认为是logN,也就是高度次。

因为堆是完全二叉树,而满二叉树也是完全二叉树,所以为了方便证明
我们使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个结点不影响最终结果):

1.1向下建堆复杂度

我们先分别算出第一层到h-1层的节点个数和该层节点的调整次数
然后再推出总的调整次数。

  • 推导

1.2向上建堆复杂度

我们先分别算出第2层到h层的节点个数和该层节点的调整次数
然后再推出总的调整次数。

  • 推导

所以向下建堆的时间复杂度是O(N),向上建堆的复杂度是O(N*logN).
所以以后我们都尽量使用向下调整建堆。因为他的效率更高。

1.3堆排序复杂度

现在我们来看一下我们堆排序的时间复杂度是多少呢?

  • 推导

    堆排序的复杂度是O(N*logN).

二.TOP-K问题

2.1思路分析

我们的堆除了可以用来排序还可以用来解决经典的TOP-K问题。
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

  • 方法一
    我们很容易想到直接排序然后取出前K个即可。
    但是这个方法有个致命缺陷。
    如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。

    我们发现这个方法在数据量太大的时候并不适用。
    那有什么其他好的方法吗?
  • 方法二
    最佳的方式就是用堆来解决,基本思路如下:
    1 .用数据集合中前K个元素来建堆
    前k个最大的元素,则建K个数的小堆
    前k个最小的元素,则建K个数的大堆
    2 . 用剩余的N-K个元素依次与堆顶元素来比较,
    如果比堆顶元素还要大或小(小堆大 大堆小)则替换堆顶元素,然后向下调整重新建堆。

将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

为什么呢?

  • 证明

    我们通过N-K次比较就可以筛选出N-K个不满足最大前K个数的数
    剩下在堆的数就是最大的前K个。
  • 疑问

我们用反证法可以得知这种情况不存在。

2.2代码实现

  • 生成数据函数
    我们先用srand生成不同的种子防止生成的随机数是伪随机数。
    然后fopen打开文件。循环生成随机数然后写入文件即可。最后关闭文件。
void CreatData()
{int n = 100000;//生成10万个数据srand(time(0));//生成不同的种子FILE* pf = fopen("test.txt", "w");//打开文件for (int i = 0; i < n; i++){int x = rand() % 100001+i;//生成随机数fprintf(pf, "%d\n", x);//写数据}fclose(pf);//关闭文件pf = NULL;
}


这样10万个数据就生成好了。

  • 比较函数

我们先接收k。然后开好k个数是堆空间。
然后从文件读取前k个数并填充到堆里面。然后建堆
然后继续读取文件里的数据直到文件末尾(返回EOF)
然后当数据大于堆顶元素是在进堆,然后重新调整建堆即可。

void test()
{int k;printf("请输入前K个数:");scanf("%d", &k);int* a = (int*)malloc(sizeof(int) * k);//开空间建堆FILE* pf = fopen("test.txt", "r");for (int i = 0; i < k; i++){fscanf(pf, "%d", &a[i]);}//填充数据for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, k, i);}//建小堆int x;while (fscanf(pf, "%d", &x) !=EOF){if (x > a[0]){a[0] = x;AdjustDown(a, k, 0);}}//对比for (int i = 0; i < k; i++){printf("%d ", a[i]);}//打印
}
  • 检验

那我们如何确保这10个数一定是最大的呢?万一我们的算法写错不是最大的前10个数怎么办?










那我们就可以在不同的地方在一些k标点。
也就是K个很大的数,确保他们是最大的前K个。
然后只需要看结果是不是这k个数即可。

大家发现结果就是我们手动给的这10个数。说明我们的程序时没问题的。

后言

这就是建堆算法复杂度分析及TOP-K问题。这里涉及到许多数学知识。大家可以多看几遍证明图。今天就分享到这里。感谢大佬们垂阅!咱们下期见!拜拜~

相关文章:

【数据结构】建堆算法复杂度分析及TOP-K问题

【数据结构】建堆算法复杂度分析及TOP-K问题 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;数据结构 文章目录 【数据结构】建堆算法复杂度分析及TOP-K问题前言一.复杂度分析1.1向下建堆复杂度1.2向上建堆复杂度1.3堆排序复杂度 二.TOP-K问…...

Thinkphp5实现前后端通过接口通讯基本操作方法

在ThinkPHP5框架中&#xff0c;实现前后端通过接口通讯是一个常见的需求&#xff0c;尤其是在开发RESTful API时。下面是一个基本的步骤指南&#xff0c;用于设置ThinkPHP5来创建API接口&#xff0c;并使前端能够通过HTTP请求与后端进行通讯。 1. 创建API模块 首先&#xff0…...

Go 语言任务编排 WaitGroup

WaitGroup 是常用的 Go 同步原语之一,用来做任务编排。它要解决的就是并发-等待的问题: 现在有一个 goroutine A 在检查点 ( checkpoint ) 等待一组 goroutine 全部完成它们的任务,如果这些 goroutine 还没全部完成任务,那么 goroutine A 就会被阻塞在检查点,直到所有的 …...

星环科技推出知识库产品 AI PC时代数据交互方式变革

随着企业业务的快速发展&#xff0c;数据量呈爆炸式增长&#xff0c;有效的知识管理成为企业面临的重要问题。企业遇到的普遍问题是大量的结构化、半结构化数据存储在不同的系统中&#xff0c;需要用多种计算机语言进行检索。而大模型彻底改变了人们和数据的交互方式&#xff0…...

10道JVM经典面试题

1、 JVM中&#xff0c;new出来的对象是在哪个区&#xff1f; 2、 说说类加载有哪些步骤&#xff1f; 3、 JMM是什么&#xff1f; 4、 说说JVM内存结构&#xff1f; 5、 MinorGC和FullGC有什么区别&#xff1f; 6、 什么是STW? 7、 什么情况下会发生堆/栈溢出&#xff1f…...

Redisson常用的数据结构及应用场景

Redisson 提供了一系列高级数据结构&#xff0c;这些数据结构封装了 Redis 的原生数据类型&#xff0c;提供了 Java API 的便利性和分布式特性。以下是 Redisson 中一些常用的数据结构&#xff0c;场景还在不断完善中&#xff1a; RBucket&#xff1a;这是一个简单的键值对存储…...

【实现100个unity特效之8】使用ShaderGraph实现2d贴图中指定部分局部发光效果

最终效果 寒冰法师 火焰法师 文章目录 最终效果寒冰法师火焰法师 素材一、功能分析实现方法基本思路Unity的Bloom后处理为什么关键部位白色&#xff1f;最终结果 二、 新建URP项目三、合并图片四、使用PS制作黑白图片方法一 手动涂鸦方法二 魔棒工具1. 拖入图片进PS&#xff0…...

Ubuntu 24.04 LTS Noble安装Docker Desktop简单教程

Docker 为用户提供了在 Ubuntu Linux 上快速创建虚拟容器的能力。但是&#xff0c;那些不想使用命令行管理容器的人可以在 Ubuntu 24.04 LTS 上安装 Docker Desktop GUI&#xff0c;本教程将提供用于设置 Docker 图形用户界面的命令…… Docker Desktop 是一个易于使用的集成容…...

XML 和 SimpleXML 入门教程

XML 和 SimpleXML 入门教程 XML&#xff08;可扩展标记语言&#xff09;是一种用于存储和传输数据的标记语言。它是一种自我描述的语言&#xff0c;允许用户定义自己的标签来表示数据。SimpleXML 是 PHP 中的一个扩展&#xff0c;用于解析和操作 XML 数据。本文将介绍 XML 和 …...

leetcode--链表类题目总结

本文作为刷题时对链表类题目的总结. 常见技巧: 引入虚拟头节点 便于处理边界情况便于对链表操作快慢双指针(判环,找环的入口等)链表逆序(推荐使用 虚拟头节点 头插法 进行逆序) 链表逆序( 头插法 虚拟头节点):链表内指定区间反转_牛客题霸_牛客网 虚拟节点:合并…...

打卡第22天------回溯算法

开始学习了,希望我可以尽快成功上岸! 一、回溯理论基础 什么是回溯法?回溯法也可以叫做回溯搜索法,它是一种搜索的方式。 回溯是递归的副产品,只要有递归就会有回溯。 回溯法的效率回溯法的本质是穷举,穷举所有可能,然后找出我们想要的答案。如果想让回溯法高效一些,可…...

Ubuntu对比两个文件内容有什么区别?

在Ubuntu&#xff08;或任何基于Linux的系统&#xff09;中&#xff0c;你可以使用多种命令行工具来比较两个文件的内容差异。以下是一些常用的方法&#xff1a; 1. **diff 命令**&#xff1a; diff 是Linux中用于比较两个文件差异的标准工具。它逐行比较文件&#xff0c;并显示…...

python:本机摄像头目标检测实时推理(使用YOLOv8n模型)

本文将介绍如何使用本机摄像头进行目标检测实时推理的python代码。 文章目录 一、下载YOLO权重文件二、环境配置三、完整代码 一、下载YOLO权重文件 https://github.com/ultralytics/ultralytics?tabreadme-ov-file 拉到网页最下面&#xff0c;选择适合的模型&#xff0c;下…...

Spark实时(四):Strctured Streaming简单应用

文章目录 Strctured Streaming简单应用 一、Output Modes输出模式 二、Streaming Table API 三、​​​​​​​​​​​​​​Triggers 1、​​​​​​​unspecified&#xff08;默认模式&#xff09; 2、​​​​​​​​​​​​​​Fixed interval micro-batches&am…...

SpringBoot上传超大文件导致OOM,完美问题解决办法

问题描述 报错: Caused by: java.lang.OutOfMemoryError at java.io.ByteArrayOutputStream.hugeCapacity(ByteArrayOutputStream.java:123) ~[?:1.8.0_381] at java.io.ByteArrayOutputStream.grow(ByteArrayOutputStream.java:117) ~[?:1.8.0_381] at java.…...

PyTorch 的各个核心模块和它们的功能

1. torch 核心功能 张量操作&#xff1a;PyTorch 的张量是一个多维数组&#xff0c;类似于 NumPy 的 ndarray&#xff0c;但支持 GPU 加速。数学运算&#xff1a;提供了各种数学运算&#xff0c;包括线性代数操作、随机数生成等。自动微分&#xff1a;torch.autograd 模块用于…...

Java开发之LinkedList源码分析

#来自ゾフィー&#xff08;佐菲&#xff09; 1 简介 LinkedList 的底层数据结构是双向链表。可以当作链表、栈、队列、双端队列来使用。有以下特点&#xff1a; 在插入或删除数据时&#xff0c;性能好&#xff1b;允许有 null 值&#xff1b;查询效率不高&#xff1b;线程不安…...

外卖霸王餐系统架构怎么选?

在当今日益繁荣的外卖市场中&#xff0c;外卖霸王餐作为一种独特的营销策略&#xff0c;受到了众多商家的青睐。然而&#xff0c;要想成功实施外卖霸王餐活动&#xff0c;一个安全、稳定且高效的架构选择至关重要。本文将深入探讨外卖霸王餐架构的选择&#xff0c;以期为商家提…...

AV1技术学习:Transform Coding

对预测残差进行变换编码&#xff0c;去除潜在的空间相关性。VP9 采用统一的变换块大小设计&#xff0c;编码块中的所有的块共享相同的变换大小。VP9 支持 4 4、8 8、16 16、32 32 四种正方形变换大小。根据预测模式选择由一维离散余弦变换 (DCT) 和非对称离散正弦变换 (ADS…...

Git操作指令

Git操作指令 一、安装git 1、设置配置信息&#xff1a; # global全局配置 git config --global user.name "Your username" git config --global user.email "Your email"2、查看git版本号 git -v # or git --version3、查看配置信息&#xff1a; git…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

前端工具库lodash与lodash-es区别详解

lodash 和 lodash-es 是同一工具库的两个不同版本&#xff0c;核心功能完全一致&#xff0c;主要区别在于模块化格式和优化方式&#xff0c;适合不同的开发环境。以下是详细对比&#xff1a; 1. 模块化格式 lodash 使用 CommonJS 模块格式&#xff08;require/module.exports&a…...

如何做好一份技术文档?从规划到实践的完整指南

如何做好一份技术文档&#xff1f;从规划到实践的完整指南 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...

NineData数据库DevOps功能全面支持百度智能云向量数据库 VectorDB,助力企业 AI 应用高效落地

NineData 的数据库 DevOps 解决方案已完成对百度智能云向量数据库 VectorDB 的全链路适配&#xff0c;成为国内首批提供 VectorDB 原生操作能力的服务商。此次合作聚焦 AI 开发核心场景&#xff0c;通过标准化 SQL 工作台与细粒度权限管控两大能力&#xff0c;助力企业安全高效…...