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

选择排序之大根堆

大根堆:树的根节点大于左右子树的结点值,这样就能保证每次从树根取的是最大值

灵魂在于HeadAdjust函数,以某节点为树根通过下落调整为大根堆,

建树思想 就是,从最后一个非终端结点开始调整以该结点为根的子树, 通过HeadAdjusth函数下落实现

排序:因为树根是最大值,每次取数根,然后与树最后一个结点交换,然后将这个点固定,树的结点数减一,调整根节点这棵树重新变为大根堆,重复依次。

#include <bits/stdc++.h> 
using namespace std;
#define inf 0x3f3f3f
void swap(int &a, int &b){int tmp=a;a=b;b=tmp;
}
//子树头节点的下落 
void HeadAdjust(int a[], int k, int len){a[0]=a[k];//暂存子树头结点//一直下落,找到最终位置 for(int i=k*2; i<=len; i*=2){if(i<len && a[i+1]>a[i])i++;//从左右儿子中找到一个最大儿子 if(a[0]>=a[i])break;//找到了最终下落位置 else{//孩子比他大,就下落 a[k]=a[i];k=i;}}a[k]=a[0];//给找到的结点写回值 
}
void BuildMaxHeap(int a[], int len){//a数组从1开始存//从最后一个非终端结点开始调整,下落; for(int i=len/2; i>=1; i--){HeadAdjust(a, i, len);}
}
void HeadSort(int a[], int len){BuildMaxHeap(a, len);//建大根堆 //每次将数跟也就是最大元素与最后一个元素交换,//再调整大根堆,每次就能确定一个未确定的最大数 for(int i=len; i>1; i--){swap(a[i], a[1]);//把最大的结点1放到树末 HeadAdjust(a, 1, i-1);//每次确定一个最大数,未确定数就少一个 } 
} 
int main()
{int a[100];int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}HeadSort(a, n);for(int i=1;i<=n;i++)cout<<a[i]<<endl;return 0;
}

相关文章:

选择排序之大根堆

大根堆&#xff1a;树的根节点大于左右子树的结点值&#xff0c;这样就能保证每次从树根取的是最大值 灵魂在于HeadAdjust函数&#xff0c;以某节点为树根通过下落调整为大根堆&#xff0c; 建树思想 就是&#xff0c;从最后一个非终端结点开始调整以该结点为根的子树&#x…...

AI的魔力:如何为开源软件注入智慧,开启无限可能

“AI的魔力&#xff1a;如何为开源软件注入智慧&#xff0c;开启无限可能” 引言&#xff1a; 在科技发展的浪潮中&#xff0c;开源软件生态一直扮演着推动创新与共享的重要角色。从Linux到Python&#xff0c;开源项目赋予了开发者全球协作的机会&#xff0c;推动了技术的飞速…...

如何在 VPS 上使用 Git 设置自动部署

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。 介绍 要了解 Git 的基本知识以及如何安装&#xff0c;请参考介绍教程。 本文将教你如何在部署应用程序时使用 Git。虽然有许多使用 Gi…...

Linux下的三种 IO 复用

目录 一、Select 1、函数 API 2、使用限制 3、使用 Demo 二、Poll 三、epoll 0、 实现原理 1、函数 API 2、简单代码模板 3、LT/ET 使用过程 &#xff08;1&#xff09;LT 水平触发 &#xff08;2&#xff09;ET边沿触发 4、使用 Demo 四、参考链接 一、Select 在…...

通过 SSH 进行WordPress网站的高级服务器管理

我在管理hostease的服务器时&#xff0c;时常需要通过SSH登录服务器进行修改。而在网站管理中&#xff0c;SSH不仅是一个基础工具&#xff0c;更是高级用户用来精细化管理和优化服务器的重要工具。通过SSH&#xff0c;你可以深入监控服务器的性能、精细管理系统资源&#xff0c…...

速盾高防cdn支持移动端独立缓存

随着移动互联网的快速发展&#xff0c;移动端网页访问量也越来越大。然而&#xff0c;移动端的网络环境相对不稳定&#xff0c;用户体验可能会受到影响。因此&#xff0c;使用高防CDN来加速移动端网页访问&#xff0c;成为越来越多网站运营者的首选。 速盾高防CDN是一种分布式…...

PMP–一、二、三模、冲刺–分类–8.质量管理

文章目录 技巧五、质量管理 一模8.质量管理--质量管理计划--质量管理计划包括项目采用的质量标准&#xff0c;到底有没有满足质量需求&#xff0c;看质量标准即可。6、 [单选] 自项目开始以来&#xff0c;作为项目经理同事的职能经理一直公开反对该项目&#xff0c;在讨论项目里…...

如何快速使用Unity 的UPR---1资源检测保姆级

关于我们的性能检测工具已经有很多了&#xff0c;比如UWA的或者是我们的Unity 的UPR 都是很好的&#xff0c;今天说一下UPR吧 官方网址 &#xff1a;UPR - Unity专业性能优化工具 这个是官方给的Demo 选择你的平台就可以 这个可以作为一个参考但是不是很建议用官方的因为我们…...

pytorch中的.clone() 和 .detach()

在PyTorch中&#xff0c;.clone() 和 .detach() 是两个用于处理张量&#xff08;Tensor&#xff09;的方法&#xff0c;它们各自有不同的用途&#xff1a; .clone()&#xff1a; .clone() 方法用于创建一个张量的副本&#xff08;深拷贝&#xff09;。这意味着原始张量和新张量…...

三十二:网络爬虫的工作原理与应对方式

随着互联网的快速发展&#xff0c;网络爬虫&#xff08;Web Crawlers&#xff09;作为一种自动化工具&#xff0c;被广泛应用于搜索引擎、数据采集、网站监控等领域。网络爬虫的作用是通过自动化程序&#xff0c;模拟人类浏览网页的行为&#xff0c;自动下载和解析网页内容&…...

nodejs相关知识介绍

1、nodejs官方文档&#xff1a; https://nodejs.org/zh-cn nodejs可以用nvm进入安装&#xff1b; 2、npm说明&#xff1a; npm官方教程&#xff1a;https://npm.p2hp.com/ npm是 Node.js 的标准包管理器&#xff0c;也就是说nodejs安装好&#xff0c;npm也就安装好了&#…...

MySQL排它锁

MySQL排它锁原理 MySQL中的排它锁&#xff08;Exclusive Lock&#xff09;&#xff0c;也称为独占锁&#xff0c;是一种确保在事务期间&#xff0c;其他事务无法对锁定数据进行读取或修改的锁机制。当一个事务对某一行数据加上排它锁后&#xff0c;其他事务无法对该行数据进行…...

HarmonyOS4+NEXT星河版入门与项目实战(22)------动画(属性动画与显示动画)

文章目录 1、属性动画图解2、案例实现-小鱼移动游戏1、代码实现2、代码解释3、资源图片4、实现效果3、显示动画4、案例修改-显示动画5、总结1、属性动画图解 这里我们用一张完整的图来汇整属性动画的用法格式和使用的主要属性范围,如下所示: 2、案例实现-小鱼移动游戏 1、代…...

Vue3 Ts 如何获取组件的类型

vue3 Ts ref 子组件 1、默认写法 typeof&#xff1a;获取ts类型 InstanceType&#xff1a;获取模版的实例 <tempolate><myComponent ref"myCompRef"> </tempolate><script setup lang"ts"> import { ref } from "vue&quo…...

RAG数据拆分之PDF

引言RAG数据简介PDF解析方法及工具代码实现总结 二、正文内容 引言 本文将介绍如何将RAG数据拆分至PDF格式&#xff0c;并探讨PDF解析的方法和工具&#xff0c;最后提供代码示例。 RAG数据简介 RAG&#xff08;关系型属性图&#xff09;是一种用于表示实体及其关系的图数据…...

【算法day1】数组:双指针算法

题目引用 这里以 1、LeetCode704.二分查找 2、LeetCode27.移除元素 3、LeetCode977.有序数组的平方 这三道题举例来说明数组中双指针的妙用。 1、二分查找 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜…...

Ubuntu 22.04 离线安装软件包

在使用最小化安装时&#xff0c;默认是不带有vim 或者nano编辑器的&#xff0c;如果你的环境不能上外网就需要离线安装。 首先你需要先找一台可以上网的ubuntu系统&#xff08;虚拟机搭建也行&#xff09;&#xff0c;下载所有的依赖包&#xff0c;然后上传到需要安装的服务器…...

网络安全——浅谈HTTP协议

HTTP请求 HTTP请求是客户端往服务端发送请求动作&#xff0c;告知服务器自己的要求。 HTTP请求由状态行、请求头、请求正文三部分组成&#xff1a; 状态行&#xff1a;包括请求方式Method、资源路径URL、协议版本Version&#xff1b;请求头&#xff1a;包括一些访问的域名、…...

鸿蒙开发-在ArkTS中制作音乐播放器

音频播放功能实现 导入音频播放相关模块 首先需要从ohos.multimedia.audio模块中导入必要的类和接口用于音频播放。例如&#xff1a; import audio from ohos.multimedia.audio;创建音频播放器实例并设置播放源 可以通过audio.createAudioPlayer()方法创建一个音频播放器实…...

Rust学习笔记_03——元组

Rust学习笔记_01——基础 Rust学习笔记_02——数组 Rust学习笔记_03——元组 文章目录 Rust学习笔记_03——元组元组1. 定义元祖2. 访问元组中的元素3. 元组的解构4. 元组不可遍历和切片5. 元组作为函数返回值6. 单元元组7. 代码演示 元组 在Rust编程语言中&#xff0c;元组&a…...

OpenClaw+百川2-13B办公自动化:会议纪要生成与邮件发送全流程

OpenClaw百川2-13B办公自动化&#xff1a;会议纪要生成与邮件发送全流程 1. 为什么需要自动化会议纪要处理 上周三的部门例会让我彻底崩溃了——2小时的会议录音&#xff0c;手动整理成纪要花了整整3小时。更糟的是&#xff0c;当我终于把邮件发出去时&#xff0c;发现漏掉了…...

索尼Bravia家庭影院新品登场,能否重塑市场格局?

索尼Bravia新品&#xff1a;模块化家庭影院新选择索尼宣布推出七款新的Bravia家庭影院产品&#xff0c;涵盖一台电视、两款条形音箱、三款低音炮和后置音箱。除Theater Bar 5外&#xff0c;产品可自由搭配组合。其中&#xff0c;Bravia Theater Bar 7作为中高端条形音箱&#x…...

vLLM-v0.17.1详细步骤:SSH远程部署+Jupyter可视化结果分析全流程

vLLM-v0.17.1详细步骤&#xff1a;SSH远程部署Jupyter可视化结果分析全流程 1. vLLM框架简介 vLLM是一个专注于大语言模型(LLM)推理和服务的高性能开源库。这个项目最初由加州大学伯克利分校的天空计算实验室开发&#xff0c;现在已经发展成为一个活跃的社区驱动项目&#xf…...

yolo系列演进分析

YOLO(You Only Look Once)作为计算机视觉领域最具影响力的目标检测算法系列之一,自2016年首次提出以来经历了持续的技术革新与架构演进。从最初的YOLOv1到2026年最新发布的YOLO26,这一系列不仅实现了从"单阶段检测"到"端到端推理"的范式转变,更在速度…...

免费降AI率和付费降AI率差距有多大?降论文ai率效果实测对比

免费降AI率和付费降AI率差距有多大&#xff1f;降论文ai率效果实测对比 “有没有免费的降AI率工具&#xff1f;” 这是毕业季被问得最多的问题之一。毕竟论文查重已经花了一笔钱&#xff0c;再加上降AI率的费用&#xff0c;对学生来说确实是一笔不小的开支。 但免费降AI率方案真…...

如何免费获取Microsoft Word APA第7版参考文献格式:完整安装指南

如何免费获取Microsoft Word APA第7版参考文献格式&#xff1a;完整安装指南 【免费下载链接】APA-7th-Edition Microsoft Word XSD for generating APA 7th edition references 项目地址: https://gitcode.com/gh_mirrors/ap/APA-7th-Edition 还在为学术论文的参考文献…...

ncmdump终极解密攻略:5分钟实现网易云音乐NCM格式无损转换

ncmdump终极解密攻略&#xff1a;5分钟实现网易云音乐NCM格式无损转换 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump 你是否曾为下载的网易云音乐只能在特定平台播放而烦恼&#xff1f;NCM格式的音乐文件像是被上了一把无形的锁&am…...

Spring_couplet_generation 结合微信小程序:春节活动创意应用开发

Spring_couplet_generation 结合微信小程序&#xff1a;春节活动创意应用开发 春节&#xff0c;是中国人最重视的传统节日。贴春联&#xff0c;更是家家户户辞旧迎新的重要仪式。但每年都买现成的春联&#xff0c;总觉得少了点新意和专属感。有没有一种方式&#xff0c;能让每…...

Halcon 标定(Calibration)与引导(Guidance)的工业实践:从理论到高精度落地的全链路解析

1. Halcon标定技术的基础认知 第一次接触Halcon标定时&#xff0c;我和很多新手一样被那些专业术语吓到了。但真正用起来才发现&#xff0c;这套系统就像给机器装上了"眼睛和尺子"。简单来说&#xff0c;标定就是教会相机看懂真实世界的尺寸和位置。想象一下&#xf…...

保姆级教程:造相Z-Image文生图模型v2快速上手,一键生成768高清图

保姆级教程&#xff1a;造相Z-Image文生图模型v2快速上手&#xff0c;一键生成768高清图 1. 为什么选择造相Z-Image模型&#xff1f; 造相Z-Image是阿里通义万相团队开源的高性能文生图扩散模型&#xff0c;拥有20亿级参数规模。相比市面上常见的512512分辨率模型&#xff0c…...