当前位置: 首页 > 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.根据备份文件中的日期判断…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...