当前位置: 首页 > 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…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

用鸿蒙HarmonyOS5实现国际象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的国际象棋小游戏的完整实现代码&#xff0c;使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├── …...