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

堆排序(c语言)

文章目录

  • 前言
  • 一.什么是堆
  • 二.向下调整算法
  • 三.堆排序的创建
  • 总结

前言

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。


一.什么是堆

堆它分两种结构逻辑结构和物理结构

逻辑结构是完全二叉树

物理结构是数组

堆还有两种特征

1.结构性:用数组表示的完全二叉树。

2.有序性:任一结点的根要大于或小于子节点:称为大堆小堆

通过向标建立父子节点的关系

左孩子(默认为child)

leftchild=parent*2+1
rightchild=parent*2+2
parent=(child-1)/2

二.向下调整算法

要想实现堆排序,首先必须知道什么是向下调整算法。

前提:左右子树都是小堆或者大堆

思路:从根节点开始,选出左右孩子中小的那一个,跟父亲比较,如果父亲小就交换,然后再往下调调到叶子节点结束

void AdjustDwon(int* a, int n, int root)
{int parent = root;//默认左孩子为childint child = parent * 2 + 1;//不能越界,所以要小于n,因为下标最高到n-1,随意当迟来的当n是出while语句while (child < n){//选出左右孩子中小的那一个//child + 1 < n如果出现只有左孩子没有右孩子的节点,就会存在越界现象if (child + 1 < n && a[child + 1] < a[child])child += 1;//如果小就交换,默认排升序if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}//如果不存在大小交换,说明已经排完了else{break;}}

三.堆排序的创建

建堆

就是先把数组转化为堆

利用向下调整算法去建立堆

思路:叶子是不用排的,从倒数最后一个非叶子的父亲开始调

	//int i = (n - 1 - 1)父亲公式for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(a, n, i);}

思考:排一个升序是建大堆还是小堆

如果是排小堆的化,每次从头顶拿出数据,就要打乱一个堆,又要把一个堆重新排,他的时间复杂度就为O(N*N),所以要用大堆排,第一个和最后一个交换,把它不看作堆里面的前N -1个数向下调整,选出最大的数再跟倒数第二个位置交换这样它的时间复杂度就为O(N*logN)。

void Heapsort(int* a, int n);
{//int i = (n - 1 - 1)父亲公式for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDwon(a, end, 0);end--;}}

四.堆的时间复杂度


总结

  堆是一种很好做调整的结构,在算法题里面使用频度很高。常用于想知道最大值或最小值的情况,比如优先级队列,作业调度等场景。

相关文章:

堆排序(c语言)

文章目录 前言一.什么是堆二.向下调整算法三.堆排序的创建总结 前言 堆排序&#xff08;Heapsort&#xff09;是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构&#xff0c;并同时满足堆积的性质&#xff1a;即子结点的键值或索引总是小于&#x…...

开源IT自动化运维工具Ansible解析

Ansible 是一款开源的 IT 自动化工具&#xff0c;用于简化应用程序部署、配置管理、持续集成、基础设施即代码&#xff08;Infrastructure as Code, IaC&#xff09;和服务编排。它由 Michael DeHaan 创建&#xff0c;并在2012年首次发布&#xff0c;到2015年被红帽公司&#x…...

【C++】仿函数优先级队列反向迭代器

目录 一、优先级队列 1、priority_queue 的介绍 2、priority_queue 的使用 3、 priority_queue 的模拟实现 1&#xff09;priority_queue()/priority_queue(first, last) 2&#xff09;push&#xff08;x&#xff09; 3&#xff09;pop&#xff08;&#xff09; 4&#…...

UE4_调试工具_绘制调试球体

学习笔记&#xff0c;仅供参考&#xff01; 效果&#xff1a; 步骤&#xff1a; 睁开眼睛就是该变量在此蓝图的实例上可公开编辑。 勾选效果&#xff1a;...

机器人路径规划:基于冠豪猪优化算法(Crested Porcupine Optimizer,CPO)的机器人路径规划(提供MATLAB代码)

一、机器人路径规划介绍 移动机器人&#xff08;Mobile robot&#xff0c;MR&#xff09;的路径规划是 移动机器人研究的重要分支之&#xff0c;是对其进行控制的基础。根据环境信息的已知程度不同&#xff0c;路径规划分为基于环境信息已知的全局路径规划和基于环境信息未知或…...

探索.NET中的定时器:选择最适合你的应用场景

概述&#xff1a;.NET提供多种定时器&#xff0c;如 System.Windows.Forms.Timer适用于UI&#xff0c;System.Web.UI.Timer用于Web&#xff0c;System.Diagnostics.Timer用于性能监控&#xff0c;System.Threading.Timer和System.Timers.Timer用于一般定时任务。在.NET 6及以上…...

5467: 【搜索】流浪奶牛

题目描述 吃不到饭的奶牛Bessie一气之下决定离开农场&#xff0c;前往阿尔费茨山脉脚底下的农场&#xff08;听说那儿的草极其美味&#xff09;投靠她的亲戚Jimmy。但是前往目的地的山路崎岖&#xff0c;Bessie又没有吃饭&#xff0c;她需要尽量保存体力&#xff0c;以最轻松的…...

spring boot整合elasticsearch实现查询功能

第一步、添加依赖&#xff08;注意版本对应关系&#xff09;根据spring boot版本选择合适的版本 <dependency><groupId>org.elasticsearch</groupId><artifactId>elasticsearch</artifactId><version>7.6.2</version></dependenc…...

白嫖阿里云程序员日历

https://developer.aliyun.com/topic/lingma/activities/202403?taskCode14508&recordId44f3187f7950776f494eec668a62c65f#/?utm_contentm_fission_1 「通义灵码 体验 AI 编码&#xff0c;开 AI 盲盒」 打开链接直接领就行了...

ubuntu20.04搭建rtmp视频服务

1.安装软件 sudo apt-get install ffmpeg sudo apt-get install nginx sudo apt-get install libnginx-mod-rtmp 2.nginx配置 修改/etc/nginx/nginx.conf文件&#xff0c;在末尾添加&#xff1a; rtmp {server {listen 1935;application live {live on;}} } 3.视频测试 本…...

Request failed with status code 504,Gateway time out

问题描述&#xff1a; 部署在测试环境的项目在执行某功能时&#xff0c;后台程序在执行过程中&#xff0c;前端控制台在一分钟左右会报出Request failed with status code 504&#xff0c;Gateway time out异常。但是在本地开发环境会正常运行&#xff0c;并不会报出异常。 问题…...

四、Elasticsearch 进阶

自定义目录 4.1 核心概念4.1.1 索引&#xff08;Index&#xff09;4.1.2 类型&#xff08;Type&#xff09;4.1.3 文档&#xff08;Document&#xff09;4.1.3 字段&#xff08;Field&#xff09;4.1.5 映射&#xff08;Mapping&#xff09;4.1.6 分片&#xff08;Shards&#…...

海外云手机如何帮助亚马逊引流?

随着全球化的推进&#xff0c;出海企业和B2B外贸企业越来越注重海外市场的开拓&#xff0c;这已成为企业争夺市场份额的重要策略。本文将重点探讨海外云手机在优化亚马逊店铺引流方面的作用和优势。 海外云手机是一种在云端运行的虚拟手机&#xff0c;能够在单一芯片上多开几个…...

Gateway新一代网关

Gateway新一代网关 1、概述 ​ Cloud全家桶中有个很重要的组件就是网关&#xff0c;在1.x版本中都是采用的Zuul网关&#xff1b; ​ 但在2.x版本中&#xff0c;zuul的升级一直跳票&#xff0c;SpringCloud最后自己研发了一个网关SpringCloud Gateway替代Zuul。 ​ 官网&…...

Simulink中Scope图像导出在MATLAB上重新画

在Simulink中&#xff0c;Scope是一个常用的可视化工具&#xff0c;用于实时显示仿真过程中的信号波形。 1. 从Simulink Scope中导出数据 首先&#xff0c;您需要在Simulink的Scope中捕获或记录想要导出的数据。这通常通过配置Scope的“Logging”选项来实现。确保在仿真过程中…...

利用opencv获取系统时间

前一篇《c获取系统时间的方法-CSDN博客》博客介绍了如何在不同系统中获取系统时间的方法&#xff0c;但这些方法受系统的限制&#xff0c;如time.h就只能在Linux系统中使用。而opencv则不受系统限制&#xff0c;示例代码如下&#xff0c; #include <opencv2/opencv.hpp>…...

Go环境变量配置,及GOROOT、GOPATH的区别

一、安装Go go下载地址&#xff1a; https://golang.google.cn/dl/ windows下载安装&#xff0c;有两种方式。解压和直接安装 方式一&#xff1a;直接下载安装包。以.msi结尾的文件。例如&#xff1a; go1.22.1.windows-amd64.msi 下载后&#xff0c;双击后一直点下一步即…...

爬虫系列-CSS基础语法

&#x1f308;个人主页&#xff1a;会编程的果子君 &#x1f4ab;个人格言:“成为自己未来的主人~” CSS全称层叠样式表 &#xff0c;主要用来定义页面内容展示效果的一门语言&#xff0c;HTML&#xff1a;页面骨架&#xff0c;素颜CSS&#xff1a;页面效果美化&#xff1a…...

获取比特币和莱特币的实时价格

数据来源&#xff1a; https://datacenter.jin10.com/reportType/dc_bitcoin_current 代码&#xff1a; import akshare as ak import pandas as pd pd.set_option(display.max_columns, None) pd.set_option(display.max_rows, None) pd.set_option(display.width, 1000)cr…...

Axure案例分享—折叠面板(附下载地址)

今天和大家分享的Axure案例是折叠面板 折叠面板是移动端APP中常见的组件之一&#xff0c;有时候也称之为手风琴。咱们先看下Axure画出的折叠面板原型效果&#xff0c;然后再对该组件进行详细讲解。 一、功能介绍 折叠或展开多个面板内容&#xff0c;默认为展开一项内容&…...

App无辜躺枪?手把手教你搞定腾讯手机管家误报导致的应用商店下架

当合规应用遭遇误报下架&#xff1a;开发者系统性应对指南运动健康类应用被标记为金融诈骗软件&#xff1f;社交工具因"病毒风险"被各大商店紧急下架&#xff1f;这类看似荒谬的误报事件&#xff0c;正在成为中小开发团队的"无妄之灾"。某知名运动App开发团…...

Windows 10/11系统下,SecureCRT 8.7.2保姆级安装与激活图文指南(含Keygen使用避坑点)

Windows平台SecureCRT 8.7.2全流程部署与安全配置指南在当今远程运维与网络管理的日常工作中&#xff0c;一款可靠的终端仿真工具如同工程师的瑞士军刀。作为行业标杆的SecureCRT&#xff0c;其8.7.2版本在Windows 10/11环境下的部署却常让新手陷入各种技术陷阱——从安装路径选…...

2026年,揭秘那些真正安全的原生态食材厂家你不可不知的秘密

随着人们生活水平的提升以及对健康的日益重视&#xff0c;选择真正安全的原生态食材已经成为许多人购买食物的标准。但市场的繁杂使得甄别真正安全的食材厂家变得愈加困难。今天&#xff0c;我将通过几个关键角度&#xff0c;为大家揭秘那些真正安全的原生态食材厂家的秘密&…...

全链路压测实战:双十一级别的流量,我是这样扛住的

作为一名在质量保障领域摸爬滚打多年的测试工程师&#xff0c;我深知传统的单接口压测在如今分布式架构下的无力感。当业务流量达到双十一这种脉冲式、高并发的级别时&#xff0c;任何一个非核心链路上的“短板”都可能引发系统性的雪崩。全链路压测不再是选择题&#xff0c;而…...

Unity UI交互进阶:手把手教你打造一个支持单击、双击、长按的万能按钮组件

Unity UI交互进阶&#xff1a;手把手教你打造一个支持单击、双击、长按的万能按钮组件在游戏开发中&#xff0c;UI交互的流畅性和多样性直接影响玩家的游戏体验。想象一下&#xff0c;当你在开发一个RPG游戏的背包系统时&#xff0c;需要实现道具的单击查看详情、双击快速使用、…...

十年以上经验的建站公司推荐|策划强、落地稳的网站制作公司盘点

互联网时代&#xff0c;企业官网已从单纯的信息展示窗口升级为集品牌价值传递、用户体验连接与业务高效转化于一体的核心数字阵地。行业报告显示&#xff0c;优质官网可帮助企业线上转化率提升35%-60%&#xff0c;而低效官网则可能导致潜在客户大量流失。面对市场上众多的网站建…...

Unity/Unreal开发者必看:用手机和陀螺仪实验,5分钟搞懂万向节死锁(附避坑指南)

Unity/Unreal开发者实战指南&#xff1a;用手机陀螺仪5分钟破解万向节死锁当你调试第一人称视角时&#xff0c;角色突然卡在墙面无法转动&#xff1b;当无人机模型在俯冲90度时失控乱转——这些很可能都是万向节死锁(Gimbal Lock)在作祟。作为实时3D开发中最恼人的数学陷阱之一…...

别再手动维护接口文档了!用Spring Boot 3和Swagger 3实现代码与文档的自动同步

Spring Boot 3与Swagger 3&#xff1a;构建零维护成本的API文档工作流 每次接口变更都要手动更新文档&#xff1f;团队成员总是抱怨文档与实际接口不一致&#xff1f;在敏捷开发时代&#xff0c;传统文档维护方式已成为拖累工程效率的典型痛点。本文将揭示如何通过Spring Boot …...

基于C#实现(WinForm)P2P聊天程序

♻️ 资源 大小&#xff1a; 29.8MB ➡️ 资源下载&#xff1a;https://download.csdn.net/download/s1t16/87430269 p2p聊天程序 一、功能介绍 1.1 登录 用户凭用户名和密码登录系统&#xff0c;可以更换服务器 IP 和端口&#xff0c;以防网络不畅通&#xff0c;连接服务…...

【2026实测】怎么提高论文原创度?盘点8款主流降AI工具,附结构级优化指南

写文章最怕碰到什么&#xff0c;是辛辛苦苦自己码出来的字&#xff0c;却被标了极高的AI值。目前很多文本审核机制对内容的原创度要求极高&#xff0c;纯手写的初稿也可能因为句式太工整被判定为机器生成的。 为了帮几个快被这事折腾疯了的学弟学妹找条出路&#xff0c;我花了…...