数据结构--堆排序(超详细!)

一、前言

堆排序与Top K问题是堆的两大应用,在我们日常也有很广泛的用处

我们已经上面已经说过了堆,这次来说堆的其中一个应用---堆排序。
 

二、堆排序

堆排序优势在哪里?有什么恐怖之处吗?

重点:拿一个举例:我们上一篇博客在代码运用过程中,我们的HeapPop函数每次删除堆顶元素之后进行向下调整之后,都能找到次大或者次小的值。

int main()
{HP php;InitHeap(&php);int a[] = { 4,7,2,3,9,5,1 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)//建堆{PushHeap(&php, a[i]);}while (!HeapEmpty(&php))//进入循环,直至堆为空{printf("%d ", HeapTop(&php));//打印堆顶元素HeapPop(&php);//删除堆顶元素}DestroyHeap(&php);return 0;
}

  这样就把我们所想要的排序好了,我们每取出一个次大或者次小的值,时间复杂度都是O(log N),当有1000个数据时,各个元素比较查找那就需要进行1000次,而我们这种做法10次就够了。效率很高。分析上面代码,还是有点缺陷的,在我们建堆的时候,我们是从源头数组里面取数据,再新开辟空间建堆,源头数组并没有变化,这便造成了空间的浪费。所以,有没有一种高效又节省空间的方法呢----堆排序。

  我们要想节省空间,最好需要做到不另开辟空间,我们已经定义了一个数组,并且想将数组里面的元素进行排序,那为什么我们不在原数组上找路子呢?

1、建堆

 开辟空间的建堆方式,先将源头数组里面的元素放入我们开辟的结构体中的数组里,再进行向上调整建堆。那为何我们不直接将源头数组元素直接进行向上调整呢?

我们可以直接将原数组传给AdjustUp函数,再先将数组中第一个元素进行向上调整,接着再第二个元素,这样依次进行向上调整。

int a[] = { 4,7,2,3,9,5,1,6,8};int n = sizeof(a) / sizeof(a[0]);int i = 0;for (i = 1; i < n; i++){AdjustUp(&a, i);}

我们打印一下看看结果:

因为我们上述向上调整函数最终调整为小堆,这里就拿小堆来做参考:

监视查看数组的变化:

  可以看到,数组中元素已经是小堆。这样既满足了我们的建堆要求,也降低了空间的消耗

2、排序

  那么,话说回来,堆是随便建的吗?直接建一个大堆或者小堆都可以满足我们要求吗?有没有什么要求呢?

  我们在开头举国一个例子:我们的HeapPop函数每次删除堆顶元素之后进行向下调整之后,都能找到次大或者次小的值。

  HeapPop函数的逻辑是,将堆顶元素A与堆尾元素B互换,然后A删除,将B向下调整建堆。

  如果刚开始建的是小堆,我们交换堆顶元素A和队尾元素B后不着急删除A,既然是小堆,那么A肯定是所有元素中的最小值,交换后在队尾。我们再进行向下调整后,重建建小堆(这里重新建堆时不要将A也加入建堆的操作中,因为我们没有删除A),这时候的堆顶元素就是次小的值。我们将堆顶元素再与倒数第二个元素进行交换,这样次小的值就在倒数第二个位置了,再进行向下调整。这两个操作多次进行,直到剩下最后一个元素。我们每次都是找次小的值将它放在数组中最后一个,这样下来,我们最终就会得到排序好的元素,为降序

  如果是大堆呢?每次向下调整都会找到次大的值,堆顶元素与堆尾元素交换后,次大的值依次从后向前排列,最后我们便得到排序好的元素,为升序。

 

所以我们可以总结出,升序建大堆,降序建小堆。

代码如下(以降序举例):

int main()
{int a[] = { 4,7,2,3,9,5,1,6,8};int n = sizeof(a) / sizeof(a[0]);int i = 0;//在数组里建堆,减少了空间消耗//升序建大堆,降序建小堆 for (i = 1; i < n; i++){AdjustUp(&a, i);}//查看建堆后的元素排列for (i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");//重新定义一个变量,将元素大小赋值给它.不改变nint end = n - 1;while(end > 0){Swap_HP(&a[0],&a[end]);//交换堆顶元素与堆尾元素AdjustDown(&a,end, 0);//向下调整找到此小值end--;//在下一次交换中,让新的堆顶元素与新的堆尾元素交换。}for (i = 0; i < n; i++){	printf("%d ", a[i]);}return 0;
}

这一趟下来时间复杂度只有N*logN,比最开始学的冒泡排序快了不少。数据越多,就越能体现出堆排序的优越性!

以上就是堆排序要说的所有内容。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/248551.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

fiber学习

React原理&#xff1a;通俗易懂的 Fiber - 掘金

泰迪智能科技生成式人工智能(AIGC)实验室解决方案

AIGC&#xff08;Artificial Intelligence Generated Content&#xff0c;生成式人工智能&#xff09;是一种新的人工智能技术&#xff0c;指的是利用人工智能技术来生成内容。这种技术可以自动生成文本、图像、音频和视频等多种类型的内容&#xff0c;而且内容的质量较高&…

Qt Excel读写 - QXlsx的安装配置以及测试

Qt Excel读写 - QXlsx的安装配置以及测试 引言一、安装配置二、简单测试 引言 Qt无自带的库处理Excel 文件&#xff0c;但可通过QAxObject 借助COM接口进行Excel的读写1。亦可使用免费的开源第三方库&#xff1a;QXlsx&#xff0c;一个基于Qt库开发的用于读写Microsoft Excel文…

Security ❀ TCP异常报文详解

文章目录 1. TCP Out-Of-Order2. TCP Previous Segment Lost3. TCP Retransmission4. TCP Dup Ack XXX#X5. TCP Windows Update6. TCP Previous segment not captured7. 异常案例分析 TCP协议中seq和ack seq的联系&#xff1a; id4的http请求报文由客户端发向服务器&#xff0…

【Prometheus】Prometheus的PromQL语句

Prometheus promQL的语法&#xff1a; #时间序列 node_cpu_guest_seconds_total{cpu"0"} 监控&#xff08;指标数据&#xff09; {标签} node使用CPU的描述的统计&#xff0c;符合标签CPU0的时间序列的查询结果 指标标签生成时间序列 标签&#xff1a; __address…

品牌时代:应对非对称性风险的战略与实践

市场环境中&#xff0c;非对称性风险成为企业必须直面的挑战。非对称性风险指的是企业在经营过程中面临的不确定性因素&#xff0c;这些因素可能导致企业遭受重大损失或获得巨大收益。为了应对这种风险&#xff0c;企业需要从产品导向转向品牌导向&#xff0c;通过品牌建设来提…

解决:ModuleNotFoundError: No module named ‘selenium’

解决&#xff1a;ModuleNotFoundError: No module named ‘selenium’ 文章目录 解决&#xff1a;ModuleNotFoundError: No module named selenium背景报错问题报错翻译报错位置代码报错原因解决方法方法一&#xff0c;直接安装方法二&#xff0c;手动下载安装方法三&#xff0…

跟着cherno手搓游戏引擎【12】渲染context和首个三角形

渲染上下文&#xff1a; 目的&#xff1a;修改WindowsWindow的结构&#xff0c;把glad抽离出来 WindowsWindow.h:新建m_Context #pragma once #include "YOTO/Window.h" #include <YOTO/Renderer/GraphicsContext.h> #include<GLFW/glfw3.h> #include…

突破瓶颈,提升开发效率:Spring框架进阶与最佳实践-IOC

IOC相关内容 1.1 bean基础配置1.1.1 bean基础配置(id与class)1.1.2 bean的name属性步骤1&#xff1a;配置别名步骤2:根据名称容器中获取bean对象步骤3:运行程序 1.1.3 bean作用范围scope配置1.1.3.1 验证IOC容器中对象是否为单例验证思路具体实现 1.1.3.2 配置bean为非单例1.1.…

ASP .NET Core Api 使用过滤器

过滤器说明 过滤器与中间件很相似&#xff0c;过滤器&#xff08;Filters&#xff09;可在管道&#xff08;pipeline&#xff09;特定阶段&#xff08;particular stage&#xff09;前后执行操作。可以将过滤器视为拦截器&#xff08;interceptors&#xff09;。 过滤器级别范围…

Redis -- 开篇热身,常用的全局命令

目录 Redis重要文件 启动停止脚本 配置文件 持久化文件存储目录 核心命令 set get 全局命令 keys exists del expire ttl 过期策略是如何实现的 定时器 type 小结 Redis重要文件 启动停止脚本 /usr/bin/redis-benchmark &#xff1a; 用于对Redis做性能基准…

搭建nginx图片服务器

&#xff08;1&#xff09;将图片存储于/home/data/images目录&#xff1b; &#xff08;2&#xff09;配置nginx.conf user nginx; worker_processes 4;error_log /var/log/nginx/error.log notice; pid /var/run/nginx.pid;events {worker_connections 10000; }ht…

编译Opencv3.3.1遇到的编译器无法识别的警告的问题解除:

问题描述&#xff1a; 本文&#xff0c;就是在一个硬件的SDK中用到了opencv3.3.1的版本&#xff0c;在笔者目前的VS2019,CUDA11版本下编译的问题和解决。在做Cmake的configure的时候&#xff0c;Cmake报了一个找不到编译器版本的错误, Selecting windows SDK version 10.0.1904…

【时间安排】

最近刚刚回到家&#xff0c;到家就是会有各种事情干扰&#xff0c;心里变乱人变懒的&#xff0c;而要做的事情也要继续&#xff0c;写论文&#xff0c;改简历&#xff0c;学习新技能。。 明天后天两天写论文改简历 周一&#xff08;早上去城市书房&#xff0c;可能吵一点戴个耳…

JVM学习

1.Java虚拟机内部有哪些线程共享&#xff0c;那些线程隔离 程序计数器&#xff1a; 通过改变这个计数器的值来选取下一条需要执行的字节码命令 Java虚拟机栈&#xff1a; 栈&#xff0c;每个方法被执行时&#xff0c;Java虚拟机都会同步的创建一个栈帧用于存储局部变量表&…

Java面试架构篇【一览众山小】

文章目录 &#x1f6a1; 简介☀️ Spring&#x1f425; 体系结构&#x1f420; 生命周期 &#x1f341; SpringMVC&#x1f330; 执行流程 &#x1f31c; SpringBoot&#x1f30d; 核心组件&#x1f38d; 自动装配&#x1f391; 3.0升级 &#x1f505; spring Cloud Alibaba&am…

数字滤波器的技术指标

文章目录 幅频特性指标异 相频特性指标各型滤波器的幅度响应表征数字滤波器频率响应特性的三个参量(1) 幅度平方响应(2) 相位响应(3) 群延迟响应 数字滤波器的技术指标一般可以用幅频特性和相频特性指标来给出。 设数字滤波器的频率响应为&#xff1a; H ( e j ω ) ∣ H ( e…

多线程事务如何回滚?

背景介绍 1&#xff0c;最近有一个大数据量插入的操作入库的业务场景&#xff0c;需要先做一些其他修改操作&#xff0c;然后在执行插入操作&#xff0c;由于插入数据可能会很多&#xff0c;用到多线程去拆分数据并行处理来提高响应时间&#xff0c;如果有一个线程执行失败&am…

构建基于Flask的跑腿外卖小程序

跑腿外卖小程序作为现代生活中的重要组成部分&#xff0c;其技术实现涉及诸多方面&#xff0c;其中Web开发框架是至关重要的一环。在这篇文章中&#xff0c;我们将使用Python的Flask框架构建一个简单的跑腿外卖小程序的原型&#xff0c;展示其基本功能和实现原理。 首先&…

echarts:获取省、市、区/县、镇的地图数据

目录 第一章 前言 第二章 获取地图的数据&#xff08;GeoJSON格式&#xff09; 2.1 获取省、市、区/县地图数据 2.2 获取乡/镇/街道地图数据 第一章 前言 需求&#xff1a;接到要做大屏的需求&#xff0c;其中需要用echarts绘画一个地图&#xff0c;但是需要的地图是区/县…