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

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...

OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
Git 命令全流程总结
以下是从初始化到版本控制、查看记录、撤回操作的 Git 命令全流程总结,按操作场景分类整理: 一、初始化与基础操作 操作命令初始化仓库git init添加所有文件到暂存区git add .提交到本地仓库git commit -m "提交描述"首次提交需配置身份git c…...

WinUI3开发_使用mica效果
简介 Mica(云母)是Windows10/11上的一种现代化效果,是Windows10/11上所使用的Fluent Design(设计语言)里的一个效果,Windows10/11上所使用的Fluent Design皆旨在于打造一个人类、通用和真正感觉与 Windows 一样的设计。 WinUI3就是Windows10/11上的一个…...
Springboot多数据源配置实践
Springboot多数据源配置实践 基本配置文件数据库配置Mapper包Model包Service包中业务代码Mapper XML文件在某些复杂的业务场景中,我们可能需要使用多个数据库来存储和管理不同类型的数据,而不是仅仅依赖于单一数据库。本技术文档将详细介绍如何在 Spring Boot 项目中进行多数…...