数据结构——排序算法——堆排序
堆排序过程如下:
1.用数列构建出一个大顶堆,取出堆顶的数字;
2.调整剩余的数字,构建出新的大顶堆,再次取出堆顶的数字;
3.循环往复,完成整个排序。
构建大顶堆有两种方式:
1.从 0 开始,将每个数字依次插入堆中,一边插入,一边调整堆的结构,使其满足大顶堆的要求;
2.将整个数列的初始状态视作一棵完全二叉树,自底向上调整树的结构,使其满足大顶堆的要求。
二更为常用
void swap(vector<int> arr, int i, int j)
{int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 调整大顶堆,第三个参数表示剩余未排序的数字的数量,也就是剩余堆的大小void maxHeapify(vector<int> arr, int i, int heapSize) {// 左子结点下标int l = 2 * i + 1;// 右子结点下标int r = l + 1;// 记录根结点、左子树结点、右子树结点三者中的最大值下标int largest = i;// 与左子树结点比较if (l < heapSize && arr[l] > arr[largest]) {largest = l;}// 与右子树结点比较if (r < heapSize && arr[r] > arr[largest]) {largest = r;}if (largest != i) {// 将最大值交换为根结点swap(arr, i, largest);// 再次调整交换数字后的大顶堆maxHeapify(arr, largest, heapSize);}
}// 构建初始大顶堆
void buildMaxHeap(vector<int> arr) {// 从最后一个非叶子结点开始调整大顶堆,最后一个非叶子结点的下标就是 arr.length / 2-1for (int i = arr.size() / 2 - 1; i >= 0; i--) {maxHeapify(arr, i, arr.size());}
}void heapSort(vector<int> arr) {// 构建初始大顶堆buildMaxHeap(arr);for (int i = arr.size() - 1; i > 0; i--) {// 将最大值交换到数组最后swap(arr, 0, i);// 调整剩余数组,使其满足大顶堆maxHeapify(arr, 0, i);}
}
相关文章:

数据结构——排序算法——堆排序
堆排序过程如下: 1.用数列构建出一个大顶堆,取出堆顶的数字; 2.调整剩余的数字,构建出新的大顶堆,再次取出堆顶的数字; 3.循环往复,完成整个排序。 构建大顶堆有两种方式: 1.从 0 开…...
【Spring事务底层实现原理】
Transactional注解 Spring使用了TransactionInterceptor拦截器,该拦截器主要负责事务的管理,包括开启、提交、回滚等操作。当在方法上添加Transactional注解时,Spring会在AOP框架中对该方法进行拦截,TransactionInterceptor会在该…...
docker快速安装redis,mysql,minio,nacos等常用软件【持续更新】
redis ①拉取镜像 docker pull redis② 创建容器 docker run -d --name redis --restartalways -p 6379:6379 redis --requirepass "PASSWORD"–requirepass “输入你的redis密码” nacos ①:docker拉取镜像 docker pull nacos/nacos-server:1.2.0②…...

SCRUM产品负责人(CSPO)认证培训课程
课程简介 Scrum是目前运用最为广泛的敏捷开发方法,是一个轻量级的项目管理和产品研发管理框架。产品负责人是Scrum的三个角色之一,产品负责人在Scrum产品开发当中扮演舵手的角色,他决定产品的愿景、路线图以及投资回报,他需要回答…...

python连接mysql数据库的练习
一、导入pandas内置的sqlite3模块,连接的信息:ip地址是本机, 端口号port 是3306, 用户user是root, 密码password是123456, 数据库database是lambda-xiaozhang import pymysql# 打开数据库连接,参数1:主机名或IP;参数…...

扩散模型在图像生成中的应用:从真实样例到逼真图像的奇妙转变
一、扩散模型 扩散模型的起源可以追溯到热力学中的扩散过程。热力学中的扩散过程是指物质从高浓度往低浓度的地方流动,最终达到一种动态的平衡。这个过程就是一个扩散过程。 在深度学习领域中,扩散模型(diffusion models)是深度生…...

Windows 打包 Docker 提示环境错误: no DOCKER_HOST environment variable
这个问题应该还是比较常见的。 [ERROR] Failed to execute goal io.fabric8:docker-maven-plugin:0.40.2:build (default) on project mq-service: Execution default of goal io.fabric8:docker-maven-plugin:0.40.2:build failed: No <dockerHost> given, no DOCKER_H…...

2023.9.8 基于传输层协议 UDP 和 TCP 编写网络通信程序
目录 UDP 基于 UDP 编写网络通信程序 服务器代码 客户端代码 TCP 基于 TCP 编写网络通信程序 服务器代码 客户端代码 IDEA 打开 支持多客户端模式 UDP 特点: 无连接性:发送端和接收端不需要建立连接也可相互通信,且每个 UDP 数据包都…...
单例模式,适用于对象唯一的情景(设计模式与开发实践 P4)
文章目录 单例模式实现代理单例惰性单例 上一章后续的内容是关于 JS 函数闭包的,考虑很多读者已经有了闭包基础或者希望通过实战理解,遂跳过上一章直接开始设计模式篇~ 需要注意的是,代码部分仅供参考,主要关注的内容是…...

C语言实现三子棋游戏(详解)
目录 引言: 1.游戏规则: 2.实现步骤: 2.1实现菜单: 2.2创建棋盘并初始化: 2.3绘制棋盘: 2.4玩家落子: 2.5电脑落子: 2.6判断胜负: 3.源码: 结语&…...

javaee之黑马乐优商城3
异步查询工具axios(儿所以时) vue官方推荐的ajax请求框架 新增品牌页面 如何找到上面这个页面 下面这个页面里面的新增商品弹窗 上面就是请求路径与请求方式 那么请求参数是什么? brand对象,外加商品分类的id数组cids (这里其实不止就是添加…...
Pytorch intermediate(二) ResNet
实现了残差网络,残差网络结构。代码比之前复杂很多 conv3x3:将输入数据进行一次卷积,将数据转换成为,残差块需要的shape大小 ResidualBlock:残差块,也是所谓的恒等块。为什么被称为恒等块,大概…...

【2023集创赛】加速科技杯作品:高光响应的二硫化铼光电探测器
本文为2023年第七届全国大学生集成电路创新创业大赛(“集创赛”)加速科技杯西北赛区二等奖作品分享,参加极术社区的【有奖征集】分享你的2023集创赛作品,秀出作品风采,分享2023集创赛作品扩大影响力,更有丰…...

编写postcss插件,全局css文件px转vw
跟目录下创建plugins文件夹,创建postcss-px-to-viewport.ts文件 文件内代码: // postcss 的插件 vite内置了postCss插件 无需安装 import { Plugin } from postcss;interface Options {viewportWidth: number }const Options {viewportWidth: 375, // …...

精品SpringCloud的B2C模式在线学习网微服务分布式
《[含文档PPT源码等]精品基于SpringCloud实现的B2C模式在线学习网站-微服务-分布式》该项目含有源码、文档、PPT、配套开发软件、软件安装教程、项目发布教程等 软件开发环境及开发工具: 开发语言:Java 框架:springcloud JDK版本…...

解决vue项目导出当前页Table为Excel
解决vue项目中导出当前页表格为Excel表格的方案 用到的技术: Vue2Element-uifile-saverxlsx 1、创建vue项目,安装element-ui 2、创建一个组件,组件内放入表格,和导出按钮 <template><div><!-- 导出的按钮 -->…...

C++设计模式_04_Strategy 策略模式
接上篇,本篇将会介绍C设计模式中的Strategy 策略模式,和上篇模板方法Template Method一样,仍属于“组件协作”模式,它与Template Method有着异曲同工之妙。 文章目录 1. 动机( Motivation)2. 代码演示Stra…...
目标检测YOLO实战应用案例100讲-基于YOLOv3多模块融合的遥感目标检测(中)
目录 2.2.3 YOLO 2.3 目标检测算法分析 2.3.1 目标检测结果评价指标...
element 表格fixed列高度无法100%
下文提到的滚动条皆为横向滚动条错误方法(旧方法,点击查看旧博客) 一下代码虽然能解决fixed列高度无法100%问题,但是会出现fixed列下面的滚动条无法被点击的问题(被fixed列遮挡),所以该方法并不…...

【接口自动化测试】Eolink Apilkit 安装部署,支持 Windows、Mac、Linux 等系统
Eolink Apikit 有三种客户端,可以依据自己的情况选择。三种客户端的数据是共用的,因此可以随时切换不同的客户端。 我们推荐使用新推出的 Apikit PC 客户端,PC 端拥有线上产品所有的功能,并且针对本地测试、自动化测试以及使用体…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...