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

Heap堆的升序排序

在heap堆中,大根堆是一种特殊的堆,它满足下列性质:对于任意一个非叶子节点i,其左右子节点的值均小于等于它本身的值。

在大根堆中,堆顶元素永远是值最大的元素,所以将堆顶元素不断取出来,就相当于对数组进行了从大到小的排序操作。

相比较于其他排序算法,使用大根堆进行数组排序的优点在于:

1:时间复杂度稳定为O(nlogn),空间复杂度仅为O(1),并且算法实现简洁、易于理解。

2:由于大根堆的特殊性质,堆排序还具有良好的局部性和稳定性,能够保持元素在排序前后的相对位置关系,不会改变具有相同值的元素之间的顺序。

下面用图片来梳理我们的思路


                                        代码注解

首先我们先创建一个数组:

1: 首先我们将数组中的值建立成大根堆

2:首尾换位,向下调整成为循环

 我们将数组中的值建立成大根堆的Adjustup函数的实现

Adjustup函数的实现的空间复杂度(3条消息) 堆的向下调整与向上调整的时间复杂度_biter down的博客-CSDN博客

我们将数组中的值建立成大根堆的Adjustup函数的实现

Adjustdown函数的实现的空间复杂度(3条消息) 堆的向下调整与向上调整的时间复杂度_biter down的博客-CSDN博客

 


                                   源码提供参考:

#include<stdio.h>
void Swap(int* p1, int* p2) {
    int t = *p1;
    *p1 = *p2;
    *p2 = t;
}

void AdjustDown(int* a, int size) {
    int parent = 0;
    //将leftchild作为最大的孩子
    int child = parent * 2 + 1;
    while (child < size)
    {
        //当leftchild的值小于rightchlid时,child的值应该为较大值的右孩子
        if (child + 1 < size && a[child + 1] > a[child])
        {
            child++;
        }
        Swap(&a[child], a[parent]);
        parent = child;
        child = child * 2 + 1;
    }
}

void AdjustUp(int* a, int child)
{
    int parent = (child - 1) / 2;
    while ( child != 0 && a[child] > a[parent])
    {
        Swap(&a[child], a[parent]);
        child  = parent;
        parent = (parent - 1) / 2;
    }
}

//排升序,建大根堆
void HeapSort(int* a,int n)
{
    //将数组中的值建立成大根堆
    for (int i = 1; i < n; ++i)
    {
        AdjustUp(a, i);
    }
    //将大根堆数组的元素升序
    for(int i=n;i>0;i--)
    {
        Swap(&a[0], &a[i]); //首尾互换
        AdjustDown(a, i); //向下调整
    }
}
int main()
{
    int arr[10] = { 2,1,5,7,6,8,0,9,4 };         //对数组进行大根堆排序
    HeapSort(arr, sizeof(arr) / sizeof(arr[0])); 
    return 0;
}

相关文章:

Heap堆的升序排序

在heap堆中&#xff0c;大根堆是一种特殊的堆&#xff0c;它满足下列性质&#xff1a;对于任意一个非叶子节点i&#xff0c;其左右子节点的值均小于等于它本身的值。 在大根堆中&#xff0c;堆顶元素永远是值最大的元素&#xff0c;所以将堆顶元素不断取出来&#xff0c;就相当…...

小程序开发收费价目表

小程序作为一种新兴应用形式&#xff0c;正在逐渐成为企业和个人推广、运营的重要手段。然而&#xff0c;小程序开发的价格因项目规模和复杂程度差异较大&#xff0c;令不少人望而却步。本文将从小程序开发的相关因素入手&#xff0c;探讨小程序开发的价格范围和算法。 一、小…...

Dubbo服务暴露步骤详解

文章目录Dubbo服务暴露步骤详解背景介绍理论知识讲解什么是服务暴露&#xff1f;Dubbo 服务暴露的基本原理操作步骤具体实现环境准备实现服务接口实现服务提供者配置 Dubbo 服务提供者启动服务提供者实现服务消费者配置 Dubbo 服务消费者测试总结Dubbo服务暴露步骤详解 背景介…...

第十四届蓝桥杯编程题部分代码题解

C. 冶炼金属 最大值就是取 a/ba / ba/b 的最小值&#xff0c;最小值就是二分找到满足 mid∗(bi1)≥aimid * (b_i 1) ≥ a_imid∗(bi​1)≥ai​ 的最小值 #include<bits/stdc.h> #define int long long #define x first #define y second using namespace std;void sol…...

统一结果封装异常处理

统一结果封装&异常处理2&#xff0c;统一结果封装2.1 表现层与前端数据传输协议定义2.2 表现层与前端数据传输协议实现2.2.1 环境准备2.2.2 结果封装步骤1:创建Result类步骤2:定义返回码Code类步骤3:修改Controller类的返回值步骤4:启动服务测试3&#xff0c;统一异常处理3…...

数字藏品平台的发展趋势是什么?

1、数字藏品平台具体内容生产模式将在PGC&#xff08;专业生产制造具体内容&#xff09;方式向PUGC&#xff08;技术专业用户生产内容&#xff09;方式变化。 目前&#xff0c;中国热门的数字藏品平台都在PGC模式中持续发展的&#xff0c;而国外流行NFT平台则比较多选用UGC&am…...

Vue3对话框(Dialog)

Vue2对话框&#xff08;Dialog&#xff09; 可自定义设置以下属性&#xff1a; 标题&#xff08;title&#xff09;&#xff0c;类型&#xff1a;string | slot&#xff0c;默认 提示 内容&#xff08;content&#xff09;&#xff0c;类型&#xff1a;string | slot&#xf…...

【深度强化学习】(5) DDPG 模型解析,附Pytorch完整代码

大家好&#xff0c;今天和各位分享一下深度确定性策略梯度算法 (Deterministic Policy Gradient&#xff0c;DDPG)。并基于 OpenAI 的 gym 环境完成一个小游戏。完整代码在我的 GitHub 中获得&#xff1a; https://github.com/LiSir-HIT/Reinforcement-Learning/tree/main/Mod…...

unity,Color.Lerp函数

介绍 Color.Lerp函数是Unity引擎中的一个静态函数&#xff0c;用于在两个颜色值之间进行线性插值&#xff0c;从而实现颜色渐变效果 方法 Color.Lerp函数是Unity引擎中的一个静态函数&#xff0c;用于在两个颜色值之间进行线性插值&#xff0c;从而实现颜色渐变效果。该函数的…...

洛谷P8799 [蓝桥杯 2022 国 B] 齿轮 C语言/C++

[蓝桥杯 2022 国 B] 齿轮 题目描述 这天&#xff0c;小明在组装齿轮。 他一共有 nnn 个齿轮&#xff0c;第 iii 个齿轮的半径为 rir_{i}ri​, 他需要把这 nnn 个齿轮按一定顺序从左到右组装起来&#xff0c;这样最左边的齿轮转起来之后&#xff0c;可以传递到最右边的齿轮&a…...

景区在线售票系统功能开发介绍

目前游客线上订票已经普及&#xff0c;景区开通线上购票渠道&#xff0c;方便游客购票&#xff0c;对于还没有开通线上购票的景区来说&#xff0c;需要提前了解一下景区线上售票系统的一些功能&#xff0c;下面给大家详细介绍一下景区在线售票需要哪些功能。 1、在线售票 包含门…...

webService的底层调用方式

webservice中采用协议Http&#xff0c;是指什么意思 WebService使用的是 SOAP (Simple Object Access Protocol)协议 Soap协议只是用来封装消息用的。封装后的消息你可以通过各种已有的协议来传输&#xff0c;比如http,tcp/ip,smtp,等等&#xff0c;你甚至还一次用自定义的协议…...

关于文件的一些小知识下

&#x1f34d;个人主页&#x1f34d;:&#x1f51c;勇敢的小牛儿&#x1f6a9; &#x1f531;推荐专栏&#x1f531;&#xff1a;C语言知识点 ⚠️座右铭⚠️&#xff1a;敢于尝试才有机会 &#x1f412;今日鸡汤&#x1f412;&#xff1a; 你受的苦 吃的亏 担的责 扛的罪 忍的…...

使用Cheat Engine与DnSpy破解Unity游戏

题目连接&#xff1a; https://play.picoctf.org/practice/challenge/361?originalEvent72&page3我们是windows系统&#xff0c;所以点击windows game下载游戏 双击运行pico.exe 屏幕上方的一串英文是叫我们找flag&#xff0c;我在这个小地图里走来走去也没flag&#xff…...

溯源取证-内存取证基础篇

使用工具&#xff1a; volatility_2.6_lin64_standalone 镜像文件&#xff1a; CYBERDEF-567078-20230213-171333.raw 使用环境&#xff1a; kali linux 2022.02 我们只有一个RAW映像文件&#xff0c;如何从该映像文件中提取出我们想要的东西呢&#xff1f; 1.Which volatili…...

Leetcode.100 相同的树

题目链接 Leetcode.100 相同的树 easy 题目描述 给你两棵二叉树的根节点 p和 q&#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 示例 1&#xff1a; 输入&#xff1a;p [1,2,3…...

每个程序员都应该知道的8大算法

在编程开发中&#xff0c;算法是用于解决特定问题或完成特定任务的一组指令或过程。算法可以用任何编程语言表示&#xff0c;可以像一系列基本操作一样简单&#xff0c;也可以像涉及不同数据结构和逻辑的多步骤过程一样复杂。 算法的主要目标是接收输入、处理它并提供预期的输…...

Nestjs实战超干货-概况-模块-Modules

模块 模块就是一个声明了装饰器Module()的类。装饰器Module()提供了元数据&#xff0c;以便让Nest组织应用程序结构。 每个应用程序至少有一个模块&#xff0c;即根模块。根模块是 Nest 用来构建应用程序图的起点&#xff0c;应用程序图是 Nest 用来解析模块和提供者关系和依赖…...

template

模板 模板注意事项 模板的函数体和声明一定要在一起&#xff0c;即放在同一个.h文件中&#xff0c;而不能将其分开到cpp和h文件中模板的编译技巧就是尽量多编译&#xff0c;模板很难查找错误模板的报错一般只有第一行有作用模板指定类型从左到右依次指定 模板推导 #pragma #…...

innovus中时序路径debug及命令使用详解?

写在前面&#xff1a;发现place结果所有与outport相关的timing check都找不到&#xff1f; 刚开始怀疑是sdc约束问题&#xff0c;check了input sdc文件及enc.dat/mmmc/mode/func.sdc 看一下是否设置了set_false_path.当然也可以用命令报出来: report_timing -unconstrained …...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

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

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

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...