当前位置: 首页 > 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;并且针对本地测试、自动化测试以及使用体…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

【WiFi帧结构】

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

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

对WWDC 2025 Keynote 内容的预测

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

如何在看板中有效管理突发紧急任务

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

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...