带你了解建堆的时间复杂度

目录
用向上调整建堆的时间复杂度
1.向上调整建堆的时间复杂度O(N*logN)
2.数学论证
3.相关代码
用向下调整建堆的时间复杂度
1.建堆的时间复杂度为O(N)
2.数学论证
3.相关代码
完结撒花✿✿ヽ(°▽°)ノ✿✿
博主建议:面试的时候可能会被面试官问到建堆时间复杂度的证明过程,最好背下来,到时候能回答出你就是最靓的仔!!!
注:堆是完全二叉树,但以满二叉树来分析的原因:
- 方便进行数学论证
- 满二叉树是特殊的完全二叉树
- 满二叉树挂的节点最多,与时间复杂度的计算一般是求是求算法的最坏运行情况相符
- 时间复杂度本来看的就是近似值,多几个节点不影响最终结果
用向上调整建堆的时间复杂度
注:一般采用的都是向下调整的方式建堆的,用向上调整建堆比较少
1.向上调整建堆的时间复杂度O(N*logN)
2.数学论证

3.相关代码
//向上调整来建堆,时间复杂度为 O(n*logN)Queue<Integer> minHeap = new PriorityQueue<>();for (int i : arr) {minHeap.offer(i);}//向上调整private void shiftUp(int child) {int parent = (child - 1) / 2;while (child > 0) {if (elem[child] > elem[parent]) {int tmp = elem[child];elem[child] = elem[parent];elem[parent] = tmp;child=parent;parent = (child - 1) / 2;} else {break;}}}
用向下调整建堆的时间复杂度
1.建堆的时间复杂度为O(N)
2.数学论证

3.相关代码
/** 创建大根堆的时间复杂度:O(N)* 以满二叉树(挂的节点最多,是特殊的完全二叉树)来分析* */public void createHeap() {for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {shiftDown(parent, usedSize);}}/** 父亲下标* 每棵树的结束下标* */private void shiftDown(int parent, int len) {//向下调整int child = parent * 2 + 1;//最起码 要有左孩子while (child < len) {//一定是有右孩子的情况下if (child + 1 < len && elem[child] < elem[child + 1]) {child++;}//点评:这代码写得有意思!!!//child下标一定是左右孩子 最大值的下标if (elem[child] > elem[parent]) {int tmp = elem[child];elem[child] = elem[parent];elem[parent] = tmp;parent = child;child = 2 * parent + 1;} else {break;}}}
完结撒花✿✿ヽ(°▽°)ノ✿✿

相关文章:
带你了解建堆的时间复杂度
目录 用向上调整建堆的时间复杂度 1.向上调整建堆的时间复杂度O(N*logN) 2.数学论证 3.相关代码 用向下调整建堆的时间复杂度 1.建堆的时间复杂度为O(N) 2.数学论证 3.相关代码 完结撒花✿✿ヽ(▽)ノ✿✿ 博主建议:面试的时候可能会被面试官问到建堆时间复杂度的证明过…...
人工智能原理(6)
目录 一、机器学习概述 1、学习和机器学习 2、学习系统 3、机器学习发展简史 4、机器学习分类 二、归纳学习 1、归纳学习的基本概念 2、变型空间学习 3、归纳偏置 三、决策树 1、决策树组成 2、决策树的构造算法CLS 3、ID3 4、决策树的偏置 四、基于实例的学习…...
单片机模块化编程文件创建流程
一、在工程文件夹下创建一个新的文件夹,命名为“ModulesCodesFiles”,译为“模块化代码文件”,用于存放所有模块化代码文件。 二、在“ModulesCodesFiles”文件夹下为每个模块创建一个新的文件夹,命名为模块的名称,例…...
docker image
docker image 1. 由来 docker image是Docker容器管理工具中的一个命令,用于管理和操作Docker镜像。 2. 常见五种示例命令和说明 以下是docker image的常见示例命令及其说明: 示例一:列出所有镜像 docker image ls描述:使用d…...
力扣75——单调栈
总结leetcode75中的单调栈算法题解题思路。 上一篇:力扣75——区间集合 力扣75——单调栈 1 每日温度2 股票价格跨度1 - 2 解题总结 1 每日温度 题目: 给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer &…...
Webpack和Parcel详解
构建工具和打包器是在开发过程中帮助组织、优化和打包项目的工具。它们可以处理依赖管理、资源优化、代码转换等任务,从而使开发流程更高效。以下是关于构建工具和打包器的一些指导: **Webpack:** Webpack 是一个功能强大的模块打包器&#…...
linux系统服务学习(六)FTP服务学习
文章目录 FTP、NFS、SAMBA系统服务一、FTP服务概述1、FTP服务介绍2、FTP服务的客户端工具3、FTP的两种运行模式(了解)☆ 主动模式☆ 被动模式 4、搭建FTP服务(重要)5、FTP的配置文件详解(重要) 二、FTP任务…...
7.原 型
7.1原型 【例如】 另外- this指向: 构造函数和原型对象中的this都指向实例化的对象 7.2 constructor属性 每个原型对象里面都有个constructor属性( constructor构造函数) 作用:该属性指向该原型对象的构造函数 使用场景: 如果有多个对象的方法&#…...
【图像分类】理论篇(2)经典卷积神经网络 Lenet~Resenet
目录 1、卷积运算 2、经典卷积神经网络 2.1 Lenet 网络构架 代码实现 2.2 Alexnet 网络构架 代码实现 2.3 VGG VGG16网络构架 代码实现 2.4 ResNet ResNet50网络构架 代码实现 1、卷积运算 在二维卷积运算中,卷积窗口从输入张量的左上角开始ÿ…...
C++系列-内存模型
内存模型 内存模型四个区代码区全局区栈区堆区内存开辟和释放在堆区开辟数组 内存模型四个区 不同区域存放的数据生命周期是不同的,更为灵活。 代码区:存放函数体的二进制代码,操作系统管理。全局区:存放全局变量,常…...
[管理与领导-30]:IT基层管理者 - 人的管理 - 向上管理,管理好你的上司,职业发展事半功倍。什么样的上司不值得跟随?
目录 前言: 一、什么是向上管理 二、为什么要向上管理 三、如何进行向上管理 四、向上管理的注意事项 五、向上管理的忌讳 六、向上管理常犯的错 七、如何帮助上司解决他关心的问题 7.1 如何帮助上司解决他关心的问题 7.2 如何帮助上司降低压力 八、什么…...
Java进阶篇--迭代器模式
目录 同步迭代器(Synchronous Iterator): Iterator 接口 常用方法: 注意: 扩展小知识: 异步迭代器(Asynchronous Iterator): 常用的方法 注意: 总结:…...
【CAM】CAM(Class Activation Mapping)——可视化CNN的特征定位
文章目录 一、CAM(Class Activation Mapping)二、CAM技术实现2.1 网络修改2.2 微调2.2 特征提取 三、总结Reference 完整代码见Github :https://github.com/capsule2077/CAM-Visualization ,如果有用可以点个Star,谢谢! 一、CAM(C…...
Maven教程_编程入门自学教程_菜鸟教程-免费教程分享
教程简介 Maven 是一款基于 Java 平台的项目管理和整合工具,它将项目的开发和管理过程抽象成一个项目对象模型(POM)。开发人员只需要做一些简单的配置,Maven 就可以自动完成项目的编译、测试、打包、发布以及部署等工作。Maven 是…...
Gof23设计模式之模板方法模式
1.定义 定义一个操作中的算法骨架,而将算法的一些步骤延迟到子类中,使得子类可以不改变该算法结构的情况下重定义该算法的某些特定步骤。 2.结构 模板方法(Template Method)模式包含以下主要角色: 抽象类࿰…...
springBoot 配置文件 spring.resources.add-mappings 参数的作用
在Spring Boot应用中,spring.resources.add-mappings参数用于控制是否将特定路径的资源文件添加到URL路径映射中。 默认情况下,该参数的值为true,即会自动将静态资源(例如CSS、JavaScript、图片等)的URL路径添加到Spr…...
《Java极简设计模式》第03章:工厂方法模式(FactoryMethod)
作者:冰河 星球:http://m6z.cn/6aeFbs 博客:https://binghe.gitcode.host 文章汇总:https://binghe.gitcode.host/md/all/all.html 源码地址:https://github.com/binghe001/java-simple-design-patterns/tree/master/j…...
C++11并发与多线程笔记(11) std::atomic续谈、std::async深入谈
C11并发与多线程笔记(11) std::atomic续谈、std::async深入谈 1、std::atomic续谈2、std::async深入理解2.1 std::async参数详述2.2 std::async和std::thread()区别:2.3 async不确定性问题的解决 1、std::atomic续谈 #include <iostream&…...
React快速入门
最近需要学到react,这里进行一个快速的入门,参考react官网 1.创建和嵌套组件 react的组件封装是个思想,我这里快速演示代码,自己本身也不太熟悉。 代码的路径是src底下的App.js function MyButton() {return (<button>I…...
windows权限维持—SSPHOOKDSRMSIDhistorySkeletonKey
windows权限维持—SSP&HOOK&DSRM&SIDhistory&SkeletonKey 1. 权限维持介绍1.1. 其他 2. 基于验证DLL加载—SPP2.1. 操作演示—临时生效2.1.1. 执行命令2.1.2. 切换用户 2.2. 操作演示—永久生效2.2.1. 上传文件2.2.2. 执行命令2.2.3. 重启生效 2.3. 总结 3. 基…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
【深尚想】TPS54618CQRTERQ1汽车级同步降压转换器电源芯片全面解析
1. 元器件定义与技术特点 TPS54618CQRTERQ1 是德州仪器(TI)推出的一款 汽车级同步降压转换器(DC-DC开关稳压器),属于高性能电源管理芯片。核心特性包括: 输入电压范围:2.95V–6V,输…...
性能优化中,多面体模型基本原理
1)多面体编译技术是一种基于多面体模型的程序分析和优化技术,它将程序 中的语句实例、访问关系、依赖关系和调度等信息映射到多维空间中的几何对 象,通过对这些几何对象进行几何操作和线性代数计算来进行程序的分析和优 化。 其中࿰…...
