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

数据结构之堆排序

  对于几个元素的关键字序列{K1,K2,…,Kn},当且仅当满足下列关系时称其为堆,其中 2i 和2i+1应不大于n。
{ K i ≤ K 2 i + 1 K i ≤ K 2 i 或 { K i ≥ K 2 i + 1 K i ≥ K 2 i {\huge \{}^{K_i≤K_{2i}} _{K_i≤K_{2i+1}} \quad\quad 或 \quad\quad {\huge \{}^{K_i≥K_{2i}} _{K_i≥K_{2i+1}} {KiK2i+1KiK2i{KiK2i+1KiK2i
  若将此序列对应的一维数组(即以一维数组作为序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不小于(或不大子) 其左、右孩子,结点的值。因此,在一个堆中,堆顶元素(即完全二义树的根结点)必为序列中的最大元素(或最小元素),并且堆中的任一棵子树也都是堆。若堆顶为最小元素,则称为小根堆;若堆顶为最大元素,则称为大根堆。
  推排序的基本思想是:对一组待排序记录的关键字,首先按堆的定义排成一个序列(即建立初始堆),从而可以输出堆项的最大关键字(对于大根堆而言),然后将剩余的关键字再调整成新堆,便得到次大的关键字,如此反复,直到全部关键字排成有序序列为止。
  初始堆的建立方法是:将待排序的关键字分放到一棵完全二叉树的各个结点中(此时完全二叉树并不一定具备堆的特性),显然,所有 i> [ n 2 ] [\frac n2] [2n]的结点 Ki 都没有子结点,以这样的 Ki 为根的子树已经是堆,因此初始建堆可从完全二叉树的第 i {i= [ n 2 ] [\frac n2] [2n]} 个结点 Ki 开始,通过调整,逐步使以K[ n 2 \frac n2 2n]、K[ n 2 \frac n2 2n]-1、K[ n 2 \frac n2 2n]-2、…、K2、K1为根的子树满足堆的定义。
  在对Ki 为根的子树建堆的过程中,可能需要交换 Ki 与K2i 或(K2i+1)的值,如此一来,以K2i(或K2i+i)为根的子树可能不再满足堆的定义,则应继续以 K2i(或K2i+1)为根进行调整。如此层层地递推下去,可能会一直延伸到叶子结点时为止。这种方法就像过筛子一样,把最大(或最小)的关键字一层一层地筛选出来,最后输出堆顶的最大(或最小) 元素。
  【函数】将一个整型数组中的元素调整成大根堆。

void HeapAdjust(int data[], int s, int m)
/*在 data[s..m]所构成的一个元素序列中,除了 data[s]外,其余元素均满足大顶堆的定义*/
/*调整元素 data[s]的位置,使 data[s..m]成为一个大顶堆*/
{int tmp,j;tmp = data[s];							/*备份元素 data[s],为其找到适当位置后再插入*/for(j= 2*s+1; j<=m; j=j*2+1){			/*沿值较大的孩子结点向下筛选*/if(j<m && data[j]<data[j+1]) ++j;	/*j是值较大的元素的下标*/if(tmp>=data[i]) break;data[s] = data[jl; s =j;			/*用s记录待插入元素的位置 (下标) */}/*for*/data[s]=tmp;							/*将备份元素插入由 s 所指出的插入位置*/
}/*HeapAdjust*/

  调整成新堆:假设输出堆顶元素之后,以堆中最后一个元素替代,那么根结点的左、右子树均为堆,此时只需自上至下进行调整即可。
  【函数】用堆排序方法对整型数组进行非递减排序。

void HeapSort(int data[], int n)		/*数组 data[0..n-1]中的n个元素进行堆排序*/
{inti;int tmp;for(i = n/2-1; i>=0; --i)			/*将 data[0..n-1]调整为大根堆*/HeapAdjust(data, i, n-1);for(i= n-l; i>0; --i){tmp=data[0]; data[0]=data[i];data[i] = tmp;					/*堆顶元素 data[0]与序列末的元素 data[i]交换*/HeapAdjust(data,0,i-1);			/*待排元素的个数减 1,将 data[0..i-1]重新调整为大根堆*/}/*for*/
}/*HeapSort*/

  为序列(55,60,40,10,80,65,15,5,75)建立初始大根堆的过程如下图所示
在这里插入图片描述

  调整为新堆过程如下图所示
在这里插入图片描述

  对于记录数较少的文件来说,堆排序的优越性并不明显,但对子大量的记录来说,堆排序是很有效的。堆排序的整个算法时间是山建立初始堆和不断调整堆这两部分时同构成的。可以证明,堆排序算法的时间复杂度为 O(n ㏒ n)。此外,堆排序只需要一个记录大小的辅助空间。堆排序是一种不稳定的排序方法。

相关文章:

数据结构之堆排序

对于几个元素的关键字序列{K1&#xff0c;K2&#xff0c;…&#xff0c;Kn}&#xff0c;当且仅当满足下列关系时称其为堆&#xff0c;其中 2i 和2i1应不大于n。 { K i ≤ K 2 i 1 K i ≤ K 2 i 或 { K i ≥ K 2 i 1 K i ≥ K 2 i {\huge \{}^{K_i≤K_{2i}} _{K_i≤K_{2i1}} …...

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之ScrollBar组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之ScrollBar组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、ScrollBar组件 鸿蒙&#xff08;HarmonyOS&#xff09;滚动条组件ScrollBar&…...

读论文:DiffBIR: Towards Blind Image Restoration with Generative Diffusion Prior

DiffBIR 发表于2023年的ICCV&#xff0c;是一种基于生成扩散先验的盲图像恢复模型。它通过两个阶段的处理来去除图像的退化&#xff0c;并细化图像的细节。DiffBIR 的优势在于提供高质量的图像恢复结果&#xff0c;并且具有灵活的参数设置&#xff0c;可以在保真度和质量之间进…...

基于微信小程序的新生报到系统的研究与实现,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

分享一下 uniapp 打包安卓apk

首先需要安装 Java 环境&#xff0c;这里就不做解释了 第二步&#xff1a;打开 mac 终端 / cmd 命令行工具 使用keytool -genkey命令生成证书 keytool -genkey -alias testalias -keyalg RSA -keysize 2048 -validity 36500 -keystore test.keystore *testalias 是证书别名&am…...

DevOps落地笔记-21|业务价值:软件发布的最终目的

上一课时介绍如何度量软件的内部质量和外部质量。在外部质量中&#xff0c;我们提到用户满意度是衡量软件外部质量的关键因素。“敏捷宣言”的第一条原则规定&#xff1a;“我们最重要的目标&#xff0c;是通过持续不断的及早交付有价值的软件使用户满意”。从这一点也可以看出…...

【动态规划】【前缀和】【数学】2338. 统计理想数组的数目

作者推荐 【动态规划】【前缀和】【C算法】LCP 57. 打地鼠 本文涉及知识点 动态规划汇总 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 LeetCode:2338. 统计理想数组的数目 给你两个整数 n 和 maxValue &#xff0c;用于描述一个 理想…...

【已解决】onnx转换为rknn置信度大于1,图像出现乱框问题解决

前言 环境介绍&#xff1a; 1.编译环境 Ubuntu 18.04.5 LTS 2.RKNN版本 py3.8-rknn2-1.4.0 3.单板 迅为itop-3568开发板 一、现象 采用yolov5训练并将pt转换为onnx&#xff0c;再将onnx采用py3.8-rknn2-1.4.0推理转换为rknn出现置信度大于1&#xff0c;并且图像乱框问题…...

多路服务器技术如何处理大量并发请求?

在当今的互联网时代&#xff0c;随着用户数量的爆炸性增长和业务规模的扩大&#xff0c;多路服务器技术已成为处理大量并发请求的关键手段。多路服务器技术是一种并行处理技术&#xff0c;它可以通过多个服务器同时处理来自不同用户的请求&#xff0c;从而显著提高系统的整体性…...

SpringBoot - 不加 @EnableCaching 标签也一样可以在 Redis 中存储缓存?

网上文章都是说需要在 Application 上加 EnableCaching 注解才能让缓存使用 Redis&#xff0c;但是测试发现不用 EnableCaching 也可以使用 Redis&#xff0c;是网上文章有问题吗&#xff1f; 现在 Application 上用了 EnableAsync&#xff0c;SpringBootApplication&#xff0…...

Linux------命令行参数

目录 前言 一、main函数的参数 二、命令行控制实现计算器 三、实现touch指令 前言 当我们在命令行输入 ls -al &#xff0c;可以查看当前文件夹下所有文件的信息&#xff0c;还有其他的如rm&#xff0c;touch等指令&#xff0c;都可以帮我们完成相应的操作。 其实运行这些…...

LLM少样本示例的上下文学习在Text-to-SQL任务中的探索

导语 本文探索了如何通过各种提示设计策略&#xff0c;来增强大型语言模型&#xff08;LLMs&#xff09;在Few-shot In-context Learning中的文本到SQL转换能力。通过使用示例SQL查询的句法结构来检索演示示例&#xff0c;并选择同时追求多样性和相似性的示例可以提高性能&…...

双非本科准备秋招(19.2)—— 设计模式之保护式暂停

一、wait & notify wait能让线程进入waiting状态&#xff0c;这时候就需要比较一下和sleep的区别了。 sleep vs wait 1) sleep 是 Thread 方法&#xff0c;而 wait 是 Object 的方法 2) sleep 不需要强制和 synchronized 配合使用&#xff0c;但 wait 强制和 s…...

使用SpringMVC实现功能

目录 一、计算器 1、前端页面 2、服务器处理请求 3、效果 二、用户登陆系统 1、前端页面 &#xff08;1&#xff09;登陆页面 &#xff08;2&#xff09;欢迎页面 2、前端页面发送请求--服务器处理请求 3、效果 三、留言板 1、前端页面 2、前端页面发送请求 &…...

spring aop实现接口超时处理组件

文章目录 实现思路实现代码starter组件 实现思路 这里使用FutureTask&#xff0c;它通过get方法以阻塞的方式获取执行结果&#xff0c;并设定超时时间&#xff1a; public V get() throws InterruptedException, ExecutionException ;public V get(long timeout, TimeUnit un…...

c++设计模式之装饰器模式

作用 为现有类增加功能 案例说明 class Car { public:virtual void show()0; };class Bmw:public Car { public:void show(){cout<<"宝马汽车>>"<<endl;} };class Audi:public Car { public:void show(){cout<<"奥迪汽车>>&q…...

WordPress如何实现随机显示一句话经典语录?怎么添加到评论框中?

我们在一些WordPress网站的顶部或侧边栏或评论框中&#xff0c;经常看到会随机显示一句经典语录&#xff0c;他们是怎么实现的呢&#xff1f; 其实&#xff0c;boke112百科前面跟大家分享的『WordPress集成一言&#xff08;Hitokoto&#xff09;API经典语句功能』一文中就提供…...

【退役之重学前端】vite, vue3, vue-router, vuex, ES6学习日记

学习使用vitevue3的所遇问题总结&#xff08;2024年2月1日&#xff09; 组件中使用<script>标签忘记加 setup 这会导致Navbar 没有暴露出来&#xff0c;导致使用不了&#xff0c;出现以下报错 这是因为&#xff0c;如果不用setup&#xff0c;就得使用 export default…...

[linux]-总线,设备,驱动,dts

1. 总线BUS 在物理层面上&#xff0c;代表不同的工作时序和电平特性&#xff1a; 总线代表着同类设备需要共同遵守的工作时序&#xff0c;不同的总线对于物理电平的要求是不一样的&#xff0c;对于每个比特的电平维持宽度也是不一样&#xff0c;而总线上传递的命令也会有自己…...

python3实现gitlab备份文件上传腾讯云COS

gitlab备份文件上传腾讯云COS 脚本说明脚本名称&#xff1a;upload.py 假设gitlab备份文件目录&#xff1a;/opt/gitlab/backups gitlab备份文件格式&#xff1a;1706922037_2024_02_06_14.2.1_gitlab_backup.tar1.脚本需和gitlab备份文件同级目录 2.根据备份文件中的日期判断…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

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

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

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...