数据结构-二叉树-堆(二)

一、建堆的时间复杂度问题

1、除了向上调整建堆,我们还可以向下调整建堆。不能在根上直接开始向下调整。这里的条件就是左右子树必须都是大堆或者小堆。我们可以倒着往前走,可以从最后一个叶子开始调整。但是从叶子开始调整没有意义。所以我们可以从倒数的第一个的非叶子开始调整。也就是最后一个叶子的父亲节点开始向下调整建堆。一层一层向上进行向下调整建堆,把大的数字往上调小的数字往下沉。那么问题来了怎么找到最后一个叶子的父亲节点。

我们先可以求出最后一个孩子的下标然后应用公式 parent = (child-1)/ 2 算出最后一个孩子的父亲节点的下标。

void HeapSort(int* a,int n)
{//首先建立大堆/*for (int i = 1; i < n; i++){UpAdjust(a, i);}*///向下调整建堆的效率要比向上调整建堆的效率要高for (int i = (n - 1 - 1) / 2; i >= 0; i--){DownAdjust(a, i, n);}//交换堆头和堆尾的数字选出最大的数字放到堆尾//然后向下调整int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);DownAdjust(a, 0, end);end--;}
}

2、向下调整和向上调整建堆的时间复杂度

向下调整:倒数第二层有2^(h-2) 个节点

建堆的调整的次数

错位相减法算出时间复杂度

每层节点个数 × 这一层最坏向下调整多少次

最后的结果为:

所以时间复杂度为O(N)  T(N) = N - h。

向上调整:

再次使用上面的错位相减法

所以时间复杂度为O(NlogN)。

因为向下调整的过程中节点多的调整的次数少,节点少的调整的次数多。向上调整的过程中节点少的调整的次数少,节点多的调整的次数多

排序调堆的时间复杂度也是O(NlogN)。

TOPK 问题

1、建N个数的大堆,再Pop k次就可以了。

2、加入N很大呢?N是100亿呢? K == 50

      1G大约十亿字节。所以是40G左右

内存中存不下,数据是在磁盘文件中。

我们可以用100亿个数中的K个数建立一个小堆。遍历剩下的数据,如果这个数据比堆顶的数据大,就替代它进堆(向下调整)最后这个小堆的数据就是最大的前K个。

void HeapTopK(int* a, int n, int k)
{//首先向下调整建堆int* topk = (int*)malloc(sizeof(int) * k);//从a数组里读for (int i = 0; i < k; i++){topk[i] = a[i];}//建立小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){DownAdjust(topk, i, k);}//遍历剩下的数如果大于堆顶的数据我们就让它进堆并向下调整for (int i = k + 1; i < n; i++){if (a[i]  > topk[0]){topk[0] = a[i];DownAdjust(topk, 0, k);}}
}

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

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

相关文章

C#开发的全套成熟的LIS系统源码JavaScript+SQLserver 2012区域云LIS系统源码

C#开发的全套成熟的LIS系统源码JavaScriptSQLserver 2012区域云LIS系统源码 医院云LIS系统是一套成熟的实验室信息管理系统&#xff0c;目前已在多家三级级医院应用&#xff0c;并不断更新。云LIS系统是为病人为中心、以业务处理为基础、以提高检验科室管理水平和工作效率为目标…

Godot3D学习笔记1——界面布局简介

创建完成项目之后可以看到如下界面&#xff1a; Godot引擎也是场景式编程&#xff0c;这里的一个场景相当于一个关卡。 这里我们点击左侧“3D场景”按钮创建一个3D场景&#xff0c;现在在中间的画面中会出现一个球。在左侧节点视图中选中“Node3D”&#xff0c;右键创建子节点…

Python打怪升级(4)

在计算机领域常常有说"合法"和"非法"指的是:是否合理&#xff0c;是否有效&#xff0c;并不是指触犯了法律。 random.randint(begin,end) 详细讲解一下这个random是指模板&#xff0c;也就是别人写好的代码直接来用&#xff0c;在Python当中&#xff0c;…

探索和构建 LLaMA 3 架构:深入探讨组件、编码和推理技术(四)分组多查询注意力

探索和构建 LLaMA 3 架构&#xff1a;深入探讨组件、编码和推理技术&#xff08;四&#xff09;分组多查询注意力 Grouped-query Attention&#xff0c;简称GQA 分组查询注意力&#xff08;Grouped-query Attention&#xff0c;简称GQA&#xff09;是多查询和多头注意力的插值…

grafana报错This panel requires Angular (deprecated)

1.原因 报错解释&#xff1a; Grafana在更新到7.0版本后&#xff0c;弃用了AngularJS&#xff08;一种用于构建大型Web应用的JavaScript框架&#xff09;。在早期的Grafana版本中&#xff0c;某些面板可能依赖于AngularJS&#xff0c;但这种依赖已经逐步被新的React或Vue面板所…

【软考经验分享】软考-中级-嵌入式备考

这里写目录标题 教辅用书嵌入式系统设计师考试大纲嵌入式系统设计师教程嵌入式系统设计师5天修炼嵌入式系统设计师考前冲刺100题 刷题软件希赛网软考真题 视频教程希赛网王道-计组计网 教辅用书 嵌入式系统设计师考试大纲 50页左右&#xff0c;内容为罗列一些考点&#xff0c…

Java基础之JVM基础调优与常见问题

常见命令 以下命令的介绍&#xff0c;全部在jdk8环境下运行的&#xff1b; jps ☆☆☆☆☆ 查看当前运行的进程号&#xff1b; jmap ☆☆☆ jmap命令可以查看jvm的内存信息&#xff0c;class对应的实例个数以及占用的内存大小 jmap -histo 查看当前java进程 [rdVM-8-12-c…

ARM学习(26)链接库的依赖查看

笔者今天来聊一下查看链接库的依赖。 通常情况下&#xff0c;运行一个可执行文件的时候&#xff0c;可能会出现找不到依赖库的情况&#xff0c;比如图下这种情况&#xff0c;可以看到是缺少了license.dll或者libtest.so&#xff0c;所以无法运行。怎么知道它到底缺少什么dll呢&…

多输入多输出 | Matlab实现WOA-LSSVM鲸鱼算法优化最小二乘支持向量机多输入多输出预测

多输入多输出 | Matlab实现WOA-LSSVM鲸鱼算法优化最小二乘支持向量机多输入多输出预测 目录 多输入多输出 | Matlab实现WOA-LSSVM鲸鱼算法优化最小二乘支持向量机多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 Matlab实现WOA-LSSVM鲸鱼算法优化…

SpringCloud系列(5)--SpringCloud微服务工程公共部分提取

前言&#xff1a;在上一章节中我们创建了两个个SpringCloud工程&#xff0c;但在两个工程中分别存在着一些重复的部分&#xff0c;例如重复的实体类&#xff08;如图所示&#xff09;&#xff0c;这样会造成系统的冗余&#xff0c;所以我们需要把公共的类提取到一个工程里&…

AOC vs. DAC:哪个更适合您的网络需求?

在现代网络通信中&#xff0c;选择合适的连接线缆对于数据传输的稳定性和速度至关重要。两种常见的线缆类型是 AOC&#xff08;Active Optical Cable&#xff09; 和 DAC&#xff08;Direct Attach Cable&#xff09;。本文将详细介绍这两种线缆的特点、优势和适用场景&#xf…

03_Scala变量和数据类型

文章目录 [toc] **变量和数据类型****1.注释****2.变量和常量****3. 标识符的命名规范****4.scala的字符串****5.键盘输入****5.1 StdIn.readLine()****5.2 从文件中读取数据****5.3 Scala向外写数据** 变量和数据类型 1.注释 和Java完全一样 ** ** 2.变量和常量 var name…

LiveNVR监控流媒体Onvif/RTSP常见问题-如何对比监控摄像头延时视频流延时支持webrtc视频流播放超低延时播放

LiveNVR如何对比监控摄像头延时视频流延时支持webrtc视频流播放超低延时播放 1、问题场景2、如何对比延时&#xff1f;3、WEBRTC延时对比4、LiveNVR支持WEBRTC输出5、RTSP/HLS/FLV/RTMP拉流Onvif流媒体服务 1、问题场景 需要低延时的视频流监控播放&#xff0c;之前可以用rtmp…

OpenHarmony实战开发-媒体查询 (@ohos.mediaquery)

概述 媒体查询作为响应式设计的核心&#xff0c;在移动设备上应用十分广泛。媒体查询可根据不同设备类型或同设备不同状态修改应用的样式。媒体查询常用于下面两种场景&#xff1a; 针对设备和应用的属性信息&#xff08;比如显示区域、深浅色、分辨率&#xff09;&#xff0…

新手Pytorch入门笔记-transforms.Compose()

我使用的图片是上图&#xff0c;直接下载即可 transforms.Compose 是PyTorch中的一个实用工具&#xff0c;用于创建一个包含多个数据变换操作的变换对象。这些变换操作通常用于数据预处理&#xff0c;例如图像数据的缩放、裁剪、旋转等。使用transforms.Compose 可以将多个数据…

如何在 Flutter 中制作多种颜色的 TextField

TextField widget 本身并不施加任何样式。相反&#xff0c;它会要求 TextEditingController 生成一个样式化的 TextSpan 对象&#xff0c;即一段带有样式的文本。 TextField 将其样式传递给 TextEditingController &#xff0c;默认实现只是将其放入 TextSpan 对象中&#xff0…

基于SSM+Vue的护工预约服务小程序和后台管理系统

1、系统演示视频&#xff08;演示视频&#xff09; 2、需要请联系

【GIS教程】ArcGIS做日照分析(附练习数据下载)

我国对住宅日照标准的规定是:冬至日住宅底层日照不少于1小时或大寒日住宅层日照不少于2小时(通常以当地冬至日正午12时的太阳高度角作为依据)。因冬至日太阳高度角最低&#xff0c;照射范围最小&#xff0c;如果冬至日12&#xff1a;00建筑物底层能够接收到阳光&#xff0c;那么…

kubernetes部署控制器Deployment

一、概念 在学习rc和rs控制器资源时&#xff0c;这两个资源都是控制pod的副本数量的&#xff0c;但是&#xff0c;他们两个有个缺点&#xff0c;就是在部署新版本pod或者回滚代码的时候&#xff0c;需要先apply资源清单&#xff0c;然后再删除现有pod&#xff0c;通过资源控制&…

[Flutter3] 记录Dio的简单封装(一)

文章目录 效果使用ResponseEntity类DioManager封装_onResponse / _onDioException 的设计Response的处理catch处理 效果 请求成功/失败/异常的日志输出效果 成功: 失败:500 失败:404 网络异常: 使用 举个使用的例子, 在调用 DioManager的时候, 直接通过返回值的状态, 来…