堆排序--C++实现
1. 简介
堆排序利用的是堆序性,最小堆进行从大到小的排序。
先建初堆,保证堆序性。将堆顶元素与最后一个元素交换,
就将当前堆中的最大(小)的元素放到了最后后。堆大小递减,再重新调整堆选出第二大,重复上述过程。
2. 实现
2.1 建初堆
由于堆具有递归性,即以根节点的所有子树都是一个堆。
我们需要从下往上调整堆。即从完全二叉树的最大非叶子节点开始调整堆,直到根节点。
这样才能保证堆序性。
对于数组3,4,1,2,5 ,建初堆的过程。

- 代码
template<typename T>
void adj_heap(std::vector<T> &arr,std::size_t rt, std::size_t bd) {T v = arr[rt];std::size_t child;std::size_t i;for (i = rt; i < bd; i = child) {child = i * 2 + 1;if ( child + 1 < bd && arr[child + 1] < arr[child])++child;if (child >= bd || v <= arr[child] ) {break;}else{arr[i] = arr[child];}}arr[i] = v;
}template<typename T>
void make_orig_heap(std::vector<T> &arr, std::size_t sz) {for (std::size_t i = sz/2 - 1; i != -1; --i){adj_heap(arr, i, sz);}
}
2.2 堆排序
建立初始堆后,我们就确定了最小(大)的元素。
将该元素与最后位置交换,并将堆大小 - 1。
我们就又得到了一个未调整的堆。我们重复调整堆和交换元素的过程,直到最后堆大小为1。
所以,最小堆进行排序形成的序列是从大到小。
过程如图

- 代码
template<typename T>
void heap_sort(std::vector<T> &arr, std::size_t sz) {if ( 0 == sz)return ;make_orig_heap(arr, sz);for (std::size_t i = sz - 1; i > 0; --i) {T last = arr[i];arr[i] = arr[0];arr[0] = last;adj_heap(arr, 0, i);}}
相关文章:
堆排序--C++实现
1. 简介 堆排序利用的是堆序性,最小堆进行从大到小的排序。 先建初堆,保证堆序性。将堆顶元素与最后一个元素交换, 就将当前堆中的最大(小)的元素放到了最后后。堆大小递减,再重新调整堆选出第二大,重复上述过程。 2…...
【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)
文章目录 4.3 字符串4.3.1 字符串的定义与存储4.3.2 字符串的基本操作4.3.3 模式匹配算法1. 算法原理2. ADL语言3. 伪代码4. C语言实现5 时间复杂度 4.3 字符串 字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是…...
VMWare虚拟机问题
镜像下载 阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区...
代码随想录算法训练营第23期day39 |62.不同路径、63. 不同路径 II
目录 一、(leetcode 62)不同路径 1.动态规划 1)确定dp数组(dp table)以及下标的含义 2)确定递推公式 3)dp数组的初始化 4)确定遍历顺序 5)举例推导dp数组 2.数论方…...
白帽黑客入门,“每天一个黑客技巧”实现黑客的自我突破 !(附工具包!)
年底了,不少朋友都是在总结一年的学习成果。最后发现完成情况与自己最初定下的目标相去甚远。 同时也针对粉丝和网上大部分存在的问题进行了整理: “为什么我感觉学安全好难?” “渗透测试到底该怎么学?” “为什么总是挖不到漏…...
Jmeter参数化 —— 循环断言多方法
1、参数化接口测试数据 注意:csv文档参数化,里面有多少条数据,就要在线程组里循环多少次,不然就只执行一次 2、添加配置元件-计数器 关于计数器 ①Starting Value:给定计数器的初始值; ②递增:每次循环迭代…...
Autosar诊断实战系列26-Dem(DTCEvent)要点及配置开发详解
本文框架 前言1. Dem及其与其他模块交互介绍1.1 与DCM模块交互1.1.1 0x14服务调用时序1.1.2 0x85服务调用时序1.1.3 0x19服务调用时序1.2 与Fim模块交互1.3 与NvM模块交互1.4 与BswM模块交互1.5 与其他BSW及APP模块交互2. Dem配置开发介绍2.1 DemGeneral配置2.1.1 DemGeneral一…...
STL(第五课):queue
STL(标准模板库)是一种C标准库,在其中包含了许多常用的数据结构和算法。其中,queue就是STL库中的一个数据结构,用于实现队列(先进先出FIFO)。 使用STL queue,需要引入头文件<queu…...
点大商城V2版 2.5.2.1 全开源独立版 多小程序端+unipp安装教程
点大商城V2是一款采用全新界面设计支持多端覆盖的小程序应用,支持H5、微信公众号、微信小程序、头条小程序、支付宝小程序、百度小程序,本程序是点大商城V2独立版,包含全部插件,代码全开源,并且有VUE全端代码。分销&am…...
Redo Log(重做日志)的刷盘策略
1. 概述 Redo Log(重做日志)是 InnoDB 存储引擎中的一种关键组件,用于保障数据库事务的持久性和崩溃恢复。InnoDB 将事务所做的更改先记录到重做日志,之后再将其应用到磁盘上的数据页。 刷盘策略(Flush Policy&#x…...
QT窗体之间值的传递,多种方法实现
目录 1. 信号和槽机制 2. 全局变量或单例模式 3. 事件过滤器 4. Qt属性系统 5. 使用QSettings类 在Qt中,有多种方法可以在窗体之间传递值。下面是一些常用的方法: 1. 信号和槽机制 使用Qt的信号和槽机制是一种常见的方式来在窗体之间传递值。您可以…...
政务服务技能竞赛中用到的软件和硬件
政务服务技能竞赛包括争上游、抢先机、秀风采、比擂台几个环节,用到选手端平板、评委端平板、主持人平板、抢答器等设备、抢答器等。分别计算团队分和个人分。答题规则和计分方案均较为复杂,一般竞赛软件无法实现,要用到高端竞赛软件…...
tcp/ip该来的还是得来
1. TCP/IP、Http、Socket的区别 \qquad 区别是:TCP/IP即传输控制/网络协议,也叫作网络通讯协议,它是在网络的使用中的最基本的通信协议。Http是一个简单的请求-响应协议,它通常运行在TCP之上。Socket是对网络中不同主机上的应用进…...
OpenCV官方教程中文版 —— 图像修复
OpenCV官方教程中文版 —— 图像修复 前言一、基础二、代码三、更多资源 前言 本节我们将要学习: • 使用修补技术去除老照片中小的噪音和划痕 • 使用 OpenCV 中与修补技术相关的函数 一、基础 在我们每个人的家中可能都会几张退化的老照片,有时候…...
前端难学还是后端难学?系统安全,web安全,网络安全是什么区别?
系统安全,web安全,网络安全是什么区别?三无纬度安全问题 系统安全,可以说是电脑软件的安全问题,比如windows经常提示修复漏洞,是一个安全问题 网页安全,网站安全,比如,…...
diffusers-Load pipelines,models,and schedulers
https://huggingface.co/docs/diffusers/using-diffusers/loadinghttps://huggingface.co/docs/diffusers/using-diffusers/loading 有一种简便的方法用于推理是至关重要的。扩散系统通常由多个组件组成,如parameterized model、tokenizers和schedulers,…...
私域营销必备:轻松掌握微信CRM管理方法
大家在微信私域营销中都遇到了什么问题? 比如管理时间不够,群发实效性低,自动回复无法适应变化等等。 我们可以利用微信CRM这个工具,轻松解决这些问题。 请问你们最想用这个工具解决什么问题呢? 使用微信CRM不仅可…...
最长回文子串-LeetCode5 动态规划
由于基础还不是很牢固 一时间只能想到暴力的解法: 取遍每个子串 总数量nn-1n-2…1 O(n^2) 判断每个子串是否属于回文串 O(n) 故总时间复杂度为O(n^3) class Solution { public:string longestPalindrome(string s) { int max0;string ret;for(int i0;i<s.size();i)for(int…...
mysql简单备份和恢复
版本:mysql8.0 官方文档 :MySQL :: MySQL 8.0 Reference Manual :: 7 Backup and Recovery 1.物理备份恢复 物理备份是以数据文件形式备份。这种方式效率高点,适合大型数据库备份。物理备份可冷备可热备。 使用mysqlbackup 命令进行物理备…...
JMeter介绍
1. JMeter是什么? 是Apache组织开发基于Java的接口测试工具,性能测试工具 2.JMeter的优缺点 优点: 开源,免费 跨平台 支持多协议 轻量级别 缺点: 不支持IP欺骗 不可验证页面UI 3.JMeter可以用来做什么? …...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
嵌入式常见 CPU 架构
架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集,单周期执行;低功耗、CIP 独立外设;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel(原始…...
LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》
🧠 LangChain 中 TextSplitter 的使用详解:从基础到进阶(附代码) 一、前言 在处理大规模文本数据时,特别是在构建知识库或进行大模型训练与推理时,文本切分(Text Splitting) 是一个…...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
使用python进行图像处理—图像滤波(5)
图像滤波是图像处理中最基本和最重要的操作之一。它的目的是在空间域上修改图像的像素值,以达到平滑(去噪)、锐化、边缘检测等效果。滤波通常通过卷积操作实现。 5.1卷积(Convolution)原理 卷积是滤波的核心。它是一种数学运算,…...
