当前位置: 首页 > news >正文

数据结构——排序算法——堆排序

堆排序过程如下:
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);}
}

相关文章:

数据结构——排序算法——堆排序

堆排序过程如下&#xff1a; 1.用数列构建出一个大顶堆&#xff0c;取出堆顶的数字&#xff1b; 2.调整剩余的数字&#xff0c;构建出新的大顶堆&#xff0c;再次取出堆顶的数字&#xff1b; 3.循环往复&#xff0c;完成整个排序。 构建大顶堆有两种方式&#xff1a; 1.从 0 开…...

【Spring事务底层实现原理】

Transactional注解 Spring使用了TransactionInterceptor拦截器&#xff0c;该拦截器主要负责事务的管理&#xff0c;包括开启、提交、回滚等操作。当在方法上添加Transactional注解时&#xff0c;Spring会在AOP框架中对该方法进行拦截&#xff0c;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 ①&#xff1a;docker拉取镜像 docker pull nacos/nacos-server:1.2.0②…...

SCRUM产品负责人(CSPO)认证培训课程

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

python连接mysql数据库的练习

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

扩散模型在图像生成中的应用:从真实样例到逼真图像的奇妙转变

一、扩散模型 扩散模型的起源可以追溯到热力学中的扩散过程。热力学中的扩散过程是指物质从高浓度往低浓度的地方流动&#xff0c;最终达到一种动态的平衡。这个过程就是一个扩散过程。 在深度学习领域中&#xff0c;扩散模型&#xff08;diffusion models&#xff09;是深度生…...

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 特点&#xff1a; 无连接性&#xff1a;发送端和接收端不需要建立连接也可相互通信&#xff0c;且每个 UDP 数据包都…...

单例模式,适用于对象唯一的情景(设计模式与开发实践 P4)

文章目录 单例模式实现代理单例惰性单例 上一章后续的内容是关于 JS 函数闭包的&#xff0c;考虑很多读者已经有了闭包基础或者希望通过实战理解&#xff0c;遂跳过上一章直接开始设计模式篇&#xff5e; 需要注意的是&#xff0c;代码部分仅供参考&#xff0c;主要关注的内容是…...

C语言实现三子棋游戏(详解)

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

javaee之黑马乐优商城3

异步查询工具axios(儿所以时) vue官方推荐的ajax请求框架 新增品牌页面 如何找到上面这个页面 下面这个页面里面的新增商品弹窗 上面就是请求路径与请求方式 那么请求参数是什么&#xff1f; brand对象&#xff0c;外加商品分类的id数组cids &#xff08;这里其实不止就是添加…...

Pytorch intermediate(二) ResNet

实现了残差网络&#xff0c;残差网络结构。代码比之前复杂很多 conv3x3&#xff1a;将输入数据进行一次卷积&#xff0c;将数据转换成为&#xff0c;残差块需要的shape大小 ResidualBlock&#xff1a;残差块&#xff0c;也是所谓的恒等块。为什么被称为恒等块&#xff0c;大概…...

【2023集创赛】加速科技杯作品:高光响应的二硫化铼光电探测器

本文为2023年第七届全国大学生集成电路创新创业大赛&#xff08;“集创赛”&#xff09;加速科技杯西北赛区二等奖作品分享&#xff0c;参加极术社区的【有奖征集】分享你的2023集创赛作品&#xff0c;秀出作品风采&#xff0c;分享2023集创赛作品扩大影响力&#xff0c;更有丰…...

编写postcss插件,全局css文件px转vw

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

精品SpringCloud的B2C模式在线学习网微服务分布式

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

解决vue项目导出当前页Table为Excel

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

C++设计模式_04_Strategy 策略模式

接上篇&#xff0c;本篇将会介绍C设计模式中的Strategy 策略模式&#xff0c;和上篇模板方法Template Method一样&#xff0c;仍属于“组件协作”模式&#xff0c;它与Template Method有着异曲同工之妙。 文章目录 1. 动机&#xff08; Motivation&#xff09;2. 代码演示Stra…...

目标检测YOLO实战应用案例100讲-基于YOLOv3多模块融合的遥感目标检测(中)

目录 2.2.3 YOLO 2.3 目标检测算法分析 2.3.1 目标检测结果评价指标...

element 表格fixed列高度无法100%

下文提到的滚动条皆为横向滚动条错误方法&#xff08;旧方法&#xff0c;点击查看旧博客&#xff09; 一下代码虽然能解决fixed列高度无法100%问题&#xff0c;但是会出现fixed列下面的滚动条无法被点击的问题&#xff08;被fixed列遮挡&#xff09;&#xff0c;所以该方法并不…...

【接口自动化测试】Eolink Apilkit 安装部署,支持 Windows、Mac、Linux 等系统

Eolink Apikit 有三种客户端&#xff0c;可以依据自己的情况选择。三种客户端的数据是共用的&#xff0c;因此可以随时切换不同的客户端。 我们推荐使用新推出的 Apikit PC 客户端&#xff0c;PC 端拥有线上产品所有的功能&#xff0c;并且针对本地测试、自动化测试以及使用体…...

Flask RESTful 示例

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

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;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 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 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 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

Linux 下 DMA 内存映射浅析

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