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

c++堆排序-建堆-插入-删除-排序

本文以大根堆为例,用数组实现,它的nums[0]是数组最大值。

时间复杂度分析:

建堆o(n)

插入删除o(logn)

堆排序O(nlogn)

首先上代码

#include<bits/stdc++.h>using namespace std;
void down(vector<int>&nums, int idx, int n)
{//删除时和由数组创建堆时用到int leftidx = 2 * idx + 1;int rightidx = 2 * idx + 2;if (leftidx >= n && rightidx >= n)return;if (rightidx >= n && nums[idx] >= nums[leftidx])return;if (rightidx < n&&nums[idx] >= nums[leftidx] && nums[idx] >= nums[rightidx])return;if (rightidx >= n || nums[leftidx] >= nums[rightidx]){swap(nums[idx], nums[leftidx]);down(nums, leftidx, n);}else{swap(nums[idx], nums[rightidx]);down(nums, rightidx, n);}
}void up(vector<int>&nums, int idx)
{//上滤操作由插入元素时用到,此处使用vector动态数组,不考虑静态数组插入元素过多导致过界拷贝扩容问题。int faridx = (idx - 1) / 2;if (idx == 0 || nums[idx] <= nums[faridx])return;swap(nums[idx], nums[faridx]);up(nums, faridx);
}void heapfy(vector<int>&nums)
{int n = nums.size();for (int i = n - 1; i >= 0; --i){if (2 * i + 1 <= n - 1)down(nums, i,n);}}void heapinsert(vector<int>&nums,int val)
{nums.emplace_back(val);int n = nums.size();up(nums, n - 1);
}void heapdel(vector<int>&nums)
{int n = nums.size();nums[0] = nums[n - 1];nums.pop_back();--n;down(nums, 0, n - 1);
}
void heapsort(vector<int>&nums)
{int n = nums.size();while (n> 1){swap(nums[0], nums[n - 1]);down(nums, 0, n-1);--n;}
}int main()
{vector<int>nums = { 2,1,4,6,5,8,0,7};heapfy(nums);for (auto& num : nums)cout << num <<" ";cout << "建队完成"<<endl;heapinsert(nums, 9);for (auto& num : nums)cout << num << " ";cout << "插入完成"<<endl;heapdel(nums);for (auto& num : nums)cout << num << " ";cout << "删除完成"<<endl;heapsort(nums);for (auto& num : nums)cout << num << " ";cout << "排序完成,堆结构已破坏" << endl;
}

读者可以复制代码到编译器里运行一下试试,帮助理解

它的主要思路参考力扣官方讲解

LeetCode 力扣官方分享 | 最大堆的基本内容和堆排序 - 知乎 (zhihu.com)

相关文章:

c++堆排序-建堆-插入-删除-排序

本文以大根堆为例&#xff0c;用数组实现&#xff0c;它的nums[0]是数组最大值。 时间复杂度分析&#xff1a; 建堆o(n) 插入删除o(logn) 堆排序O(nlogn) 首先上代码 #include<bits/stdc.h>using namespace std; void down(vector<int>&nums, int idx, i…...

使用代理后pip install 出现ssl错误

window直接设置代理 httphttp://127.0.0.1:7890;httpshttp://127.0.0.1...

护眼灯什么价位的好?最具性价比的护眼台灯推荐

到了晚上光线比较弱&#xff0c;这时候就需要开灯&#xff0c;要是孩子需要近距离看字学习等等&#xff0c;给孩子选择的灯具要特别的重视。护眼灯就是目前颇受学生家长青睐的灯具之一&#xff0c;越来越多的人会购买一个护眼灯给自己的孩子让孩子能够在灯光下学习的时候&#…...

vue event bus 事件总线

vue event bus 事件总线 创建 工程&#xff1a; H:\java_work\java_springboot\vue_study ctrl按住不放 右键 悬着 powershell H:\java_work\java_springboot\js_study\Vue2_3入门到实战-配套资料\01-随堂代码素材\day04\准备代码\08-事件总线-扩展 vue --version vue crea…...

深信服云桌面用户忘记密码后的处理

深信服云桌面用户忘记了密码&#xff0c;分两种情况&#xff0c;一个是忘记了登录深信服云桌面的密码&#xff0c;另外一个是忘记了进入操作系统的密码。 一、忘记了登录深信服云桌面的密码 登录虚拟桌面接入管理系统界面&#xff0c;在用户管理中选择用户后&#xff0c;点击后…...

Cocos Creator3.8 实战问题(一)cocos creator prefab 无法显示内容

问题描述&#xff1a; cocos creator prefab 无法显示内容&#xff0c; 或者只显示一部分内容。 creator编辑器中能看见&#xff1a; 预览时&#xff0c;看不见内容&#xff1a; **问题原因&#xff1a;** prefab node 所在的layer&#xff0c;默认是default。 解决方法&…...

朴素贝叶斯深度解码:从原理到深度学习应用

目录 一、简介贝叶斯定理的历史和重要性定义例子 朴素贝叶斯分类器的应用场景定义例子常见应用场景 二、贝叶斯定理基础条件概率定义例子 贝叶斯公式定义例子 三、朴素贝叶斯算法原理基本构成定义例子 分类过程定义例子 不同变体定义例子 四、朴素贝叶斯的种类高斯朴素贝叶斯&a…...

RUST 每日一省:闭包

Rust中的闭包是一种可以存入外层函数中变量或作为参数传递给其他函数的匿名函数。你可以在一个地方创建闭包&#xff0c;然后在不同的上下文环境中调用该闭包来完成运算。和一般的函数不同&#xff0c;闭包可以从定义它的作用域中捕获值。 语法 闭包由“||”和“{}”组合而成。…...

Ubuntu下文件的解压缩操作:常用zip和unzip

Ubuntu下文件的解\压缩 压缩一个文件夹为zip包&#xff0c;加参数-r&#xff1a; zip -r MyWeb.zip MyWeb需要排除目录里某个文件夹&#xff1f;例如我要去掉node_modules&#xff0c;以显著减小压缩包体积&#xff0c;此时该怎么做&#xff1f; zip -r MyWeb.zip ./MyWeb…...

Linux学习第22天:Linux中断驱动开发(一): 突如其来

Linux版本号4.1.15 芯片I.MX6ULL 大叔学Linux 品人间百味 思文短情长 中断作为驱动开发中很重要的一个概念&#xff0c;在实际的项目实践中经常用到。本节的主要内容包括中断简介、硬件原理分析、驱动程序开发及运行测试。其中驱动程…...

IDEA 2019 Springboot 3.1.3 运行异常

项目场景&#xff1a; 在IDEA 2019 中集成Springboot 3.1.3 框架&#xff0c;运行异常。 <?xml version"1.0" encoding"UTF-8"?><project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSch…...

【JAVA】飞机大战

代码和图片放在这个地址了&#xff1a; https://gitee.com/r77683962/fighting/tree/master 最新的代码运行&#xff0c;可以有两架飞机&#xff0c;分别通过WASD&#xff08;方向&#xff09;&#xff0c;F&#xff08;发子弹&#xff09;&#xff1b;上下左右&#xff08;控…...

Midjourney 生成油画技巧

基本 prompt oil painting, a cute corgi dog surrounded with colorful flowers技法 Pointillism 点描绘法 笔刷比较细&#xff0c;图像更精细 oil painting, a cute corgi dog surrounded with colorful flowers, pontillismImpasto 厚涂绘法 笔刷比较粗&#xff0c;图像…...

26559-2021 机械式停车设备 分类

声明 本文是学习GB-T 26559-2021 机械式停车设备 分类. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 本文件规定了机械式停车设备的分类及有关的型式、型号和适停汽车组别、尺寸及质量。 本文件适用于 GB/T 3730.1—2001定义的乘用车及商用…...

xxe攻击(XML外部实体)

1.定义 XML用于标记电子文件使其具有结构性的标记语言&#xff0c;可以用来标记数据、定义数据类型&#xff0c;是一种允许用户对自己的标记语言进行定义的源语言。XML文档结构包括XML声明、DTD文档类型定义&#xff08;可选&#xff09;、文档元素。 http://www.w3school.com.…...

大数据-hadoop

1.hadoop介绍 1.1 起源 1.2 版本 1.3生产环境版本选择 Hadoop三大发行版本:Apache、Cloudera、Hortonworks Apache版本最原始的版本 Cloudera在大型互联网企业中用的较多 Hortonworks文档较好 1.4架构 hadoop由三个模块组成 分布式存储HDFS 分布式计算MapReduce 资源调度引擎Y…...

容器启动报错

容器启动报错 docker: Error response from daemon: driver failed programming external connectivity on endpoint XXX 如下&#xff1a; 据百度&#xff1a; 在docker启动后在&#xff0c;再对防火墙firewalld进行操作&#xff0c;就会发生上述报错 详细原因&#xff1a…...

求生之路2服务器搭建插件安装及详细的游戏参数配置教程linux

求生之路2服务器搭建插件安装及详细的游戏参数配置教程linux 大家好我是艾西&#xff0c;在上一篇文章中我用windows系统给搭建演示了一遍怎么搭建自己的L4D2游戏。 那么也有不少小伙伴想知道linux系统的搭建方式以及在这个过程中有什么区别。 那么艾西今天就跟大家分享下用lin…...

IntelliJ IDEA 左侧Commit栏不见了

1.点击File->Settings->Version Control->Commit 2.勾选Use non-modal commit interface...

使用自功率谱、互功率谱估计滤波器幅频特性

这段时间终于对工程中的随机信号的一般处理方式有点头绪了&#xff0c;功率谱密度估计是十分重要的方式之一&#xff0c;仍需继续深入细化相关内容。 示例&#xff1a;使用自功率谱、互功率谱估计滤波器幅频特性&#xff0c;自己实现 & Matlab自带函数实现。 clc;clear;cl…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...