数据结构——排序算法——堆排序
堆排序过程如下:
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 端拥有线上产品所有的功能,并且针对本地测试、自动化测试以及使用体…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...

聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...

Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...

Linux 下 DMA 内存映射浅析
序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存,但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程,可以参考这篇文章,我觉得写的非常…...