「数组」堆排序 / 大根堆优化(C++)

目录

概述

核心概念:堆

堆结构

数组存堆

思路

算法过程

up()

down()

Code

优化方案

大根堆优化

Code(pro)

复杂度

总结


概述

在「数组」快速排序 / 随机值优化|小区间插入优化(C++)中,我们介绍了三种基本排序中的冒泡排序与分治思想结合的算法:快速排序。

本文我们来讲第二种基本排序:选择排序与分治思想结合的产物:堆排序。

我们来回想选择排序:每次选出最小的元素放在数组头部位置,每次都扫描一遍整个数组,整体表现为O(n²)。

我们希望只进行少量比较就能得出数组中的最小元素,该怎么做呢?堆这种结构给了我们一点启发。


核心概念:堆

堆是一颗完全二叉树,它的特点是可以用一维数组来储存。

堆结构

在初学数组排序阶段就理解二叉树似乎有些困难,不过好在我们不必完全了解二叉树的所有概念。

我们只需要知道:

①一个堆是一个层状结构,除去最底一层,每层的每个节点都有左子节点和右子节点,层层布满。

节点从上到下,从左到右依次编号。

(对于这样的结构,我们称之为二叉树,每个父节点都有左右孩子指针指向子节点。) 

②只有最后一层允许节点不排满,但节点的排布仍然是严格从左到右的。

如下,图一和图二都是堆,但图三不是堆,因为它的最底层排布不是从左到右的。

 ③堆有两种:小根堆和大根堆。

小根堆要求父节点的值小于它的两个孩子,大根堆要求父节点的值大于它的两个孩子。

我们称二叉树的头结点为根,所以这种命名就很好理解了:小根堆的根最小,大根堆的根最大。

数组存堆

此时此刻我们完全不必知道二叉树的标准结构,因为数组就可以储存堆

观察:

我们发现,一个序号从0开始的堆结构,

对于第idx个节点:

父节点序号:(idx-1)/2。

左子节点序号:idx*2+1。

右子节点序号:idx*2+2。

也就是说,对于上图这样的堆,我们将它存入数组应该是这样的:

        i   0    1    2    3    4    5    6
int arr[i]  10   15   30   40   50   100  40

因此,对于一个堆,我们可以用数组来表示它。 


思路

堆这种结构只是为我们的选择排序优化服务的。

选择排序需要我们每次找到最小的元素,那么我们不妨对数组建堆(又称堆化),获得一个小根堆数组后,堆顶,也就是序号为0的数组位置,自然就是我们要的最小元素。

获得最小元素后堆顶出堆,对剩余元素重新堆化,堆顶每次都是剩余元素中的最小元素。

我们不断进行堆顶出堆,就实现了选择排序。 

考虑到堆化是按层实现的,因此若有n个元素,则有logn层,重新堆化的过程中内部重排最多进行logn次,通过logn次比较获得最小元素,这显然优于暴力选择排序。


算法过程

堆排序由两个操作构成:上浮up和下沉down。

我们先用宏定义描述一下节点父子关系,另有swap函数实现功能封装:

#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void swap(int& a, int& b) {int temp = b;b = a, a = temp;
}

up()

对数组进行初始堆化时,依靠上浮实现。

将堆的大小称为size,数组的整体长度称为len。

我们将数组arr分割成两部分:已经堆化的[0,size),未堆化的剩余部分[size,len)

我们将剩余部分的第一个数加入堆中,它显然处于堆底,为了让它处于小根堆中合适的位置,我们进行对它上浮操作。

int size = 0;
for (int i = 0; i < len; i++) {up(arr, i);size++;
}

当idx为0时,不再上浮,否则判断此节点与其父亲的大小关系。

我们维护小根堆,所以如果父节点较大,则两者进行交换,使得父节点较小。

然后跟踪父节点,对父节点继续执行上浮操作。(这里的递归操作顺理成章的出现了)

void up(int arr[], int idx) {if (idx && arr[father(idx)] > arr[idx]) {swap(arr[father(idx)], arr[idx]);up(arr, father(idx));}
}

down()

数组完全堆化后,我们开始进行堆顶出堆,实现选择排序。

我们使用小根堆,因此需要一个额外的辅助空间来承载结果(后续它会被我们的优化方案优化掉)。

堆顶出堆后将堆中的最后一个元素赋给堆顶,堆size缩小,然后开始对堆顶执行下沉操作。

int* assist = new int[len];
for (int j = 0; j < len; j++) {assist[j] = arr[0];arr[0] = arr[--size];down(arr,0,size);
}
memcpy(arr, assist, sizeof(int) * len);
delete[] assist;

定义pos,

①如果idx节点的左右孩子没有超出数组堆化范围,则pos等于左右孩子中较小的元素的索引,这是为了使得较小的元素总是位于堆的上部。

②如果idx的右孩子超出堆化范围,那么堆中只有左孩子是有效的,pos等于左孩子。

③如果idx的左孩子也超出堆化范围,说明idx已经在堆中沉底,没有后续元素,不必比较直接返回。

当pos位的元素小于idx位的元素时,两者作交换(即idx较大时,与其最小的子节点交换),然后跟踪pos,继续下沉。 

void down(int arr[], int idx, int size) {int pos;if (rchild(idx) < size)pos = arr[lchild(idx)] < arr[rchild(idx)] ? lchild(idx) : rchild(idx);else if (lchild(idx) < size)pos = lchild(idx);else return;if (arr[idx] > arr[pos]) {swap(arr[idx], arr[pos]);down(arr,pos,size);}
}

Code

#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void up(int arr[], int idx) {if (idx && arr[father(idx)] > arr[idx]) {swap(arr[father(idx)], arr[idx]);up(arr, father(idx));}
}
void down(int arr[], int idx, int size) {int pos;if (rchild(idx) < size)pos = arr[lchild(idx)] < arr[rchild(idx)] ? lchild(idx) : rchild(idx);else if (lchild(idx) < size)pos = lchild(idx);else return;if (arr[idx] > arr[pos]) {swap(arr[idx], arr[pos]);down(arr,pos,size);}
}
void heap_sort(int arr[], int len) {int size = 0;for (int i = 0; i < len; i++) {size++;up(arr, i);}int* assist = new int[len];for (int j = 0; j < len; j++) {assist[j] = arr[0];arr[0] = arr[--size];down(arr,0,size);}memcpy(arr, assist, sizeof(int) * len);delete[] assist;
}

优化方案

辅助数组assist看起来很愚蠢,我们来像个办法处理掉它。

大根堆优化

我们何不使用大跟堆来依次弹出数组的最大元素呢?

小根堆是从前往后进行最小值选择排序,因此无法安放在原始数组中(因为堆化部分会占据数组的前面部分),但大根堆解决了这个问题。

考虑到弹出时堆size收缩,因此数组的末尾会空出一个位置,我们可以直接将弹出元素安放到该位置上。

Code(pro)

#define father(x) ((x-1)/2)
#define lchild(x) (2*x+1)
#define rchild(x) (2*x+2)
void bigger_up(int arr[], int idx) {if (idx && arr[father(idx)] < arr[idx]) {swap(arr[father(idx)], arr[idx]);bigger_up(arr, father(idx));}
}
void smaller_down(int arr[], int idx, int size) {int pos;if (rchild(idx) < size)pos = arr[lchild(idx)] > arr[rchild(idx)] ? lchild(idx) : rchild(idx);else if (lchild(idx) < size)pos = lchild(idx);else return;if (arr[idx] < arr[pos]) {swap(arr[idx], arr[pos]);smaller_down(arr, pos, size);}
}
void HPsort(int arr[], int len) {int size = 0;for (int i = 0; i < len; i++,size++) bigger_up(arr, i);while (size--) {swap(arr[0], arr[size]);smaller_down(arr, 0, size);}
}

*注意*:大根堆上浮大元素,沉底小元素。 


复杂度

时间复杂度:O(nlogn)

空间复杂度:O(logn)

复杂度分析

时间分析:{

考虑堆化是按层实现的,因此若有n个元素,则有logn层。

对n个元素建堆,每个元素按层上浮,最多比较logn次,得到O(nlogn)

对n个元素出堆,弹出堆顶后将堆尾赋给堆顶,每个元素按层下沉,最多比较logn次,得到O(nlogn)

O(nlogn)+O(nlogn)=O(2nlogn)=O(nlogn)。

}

空间分析:{

使用大跟堆建堆时,不使用额外空间承载答案。

建堆和出堆时调用递归函数进行压栈,函数最多调用logn层,最多占据空间O(logn)。

}


总结

堆为我们提供了一种新的视角来处理数组的最小元素,它的另一个重大用途就是实现优先队列priority_queue。

堆排序的分治策略也比较新颖:他不是在算法思想上进行分治,而是利用模拟堆这种数据结构进行分治,希望可以为你带来对分治思想的新启发。

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

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

相关文章

Java工具插件

一、springboot集成mqtt订阅 阿里云MQTT使用教程_复杂的世界311的博客-CSDN博客_阿里云mqtt 阿里云创建MQTT服务 先找到产品与服务,然后选择物联网平台,找到公共实例,创建一个产品。 创建产品 然后在左侧下拉栏找到设备管理,在设备管理下拉栏找到设备,然后添加设备。添加…

博客建站9 - hexo网站如何提升markdown文档的编辑效率和体验

1. 本网站的系统架构2. 场景概述3. 影响效率的问题和解决方案 3.1. 图片插入-根据文章来分类管理 3.1.1. 效率问题3.1.2. 解决方案 3.2. 图片插入-从剪贴板中插入图片 3.2.1. 效率问题3.2.2. 解决方案 3.3. 图片插入-在VSCode中预览图片 3.3.1. 效率问题3.3.2. 解决方案 3.4. 提…

【软考】设计模式之责任链模式

目录 1. 说明2. 应用场景3. 结构图4. 构成5. 适用性6. 优点7. 缺点8. java示例 1. 说明 1.使多个对象都有机会处理请求&#xff0c;从而避免请求的发送者和接收者之间的耦合关系。2.将这些对象连成一条链&#xff0c;并沿着这条链传递该请求&#xff0c;直到有一个对象处理它为…

个人学习笔记7-5:动手学深度学习pytorch版-李沐

#人工智能# #深度学习# #语义分割# #计算机视觉# #神经网络# 计算机视觉 13.10 转置卷积 例如&#xff0c;卷积层和汇聚层&#xff0c;通常会减少下采样输入图像的空间维度&#xff08;高和宽&#xff09;。然而如果输入和输出图像的空间维度相同&#xff0c;在以像素级分类…

c++基础入门二

C基础入门(二) 一、函数重载 在自然语言中&#xff0c;一句话或者一个词有不同的意思。例如&#xff1a;国乒和别人比赛是“谁也赢不了”&#xff0c;而国足和别人比赛是“谁也赢不了” 函数重载&#xff1a;是函数的一种特殊情况&#xff0c;C允许在同一作用域中声明几个功…

浪潮信息金风慧能:打造智慧新能源运营平台

近来&#xff0c;浪潮信息携手北京金风慧能技术有限公司&#xff08;简称“金风慧能”&#xff09;&#xff0c;共同发布了新能源场站集控中心的创新解决方案。该方案深度融合了浪潮信息的前沿服务器技术、软硬件一体化超融合方案及边缘计算产品与金风慧能自主研发的GW SCADA S…

C++进阶:多态

✨✨所属专栏&#xff1a;C✨✨ ✨✨作者主页&#xff1a;嶔某✨✨ 多态的概念 多态(polymorphism)的概念&#xff1a;通俗来说&#xff0c;就是多种形态。多态分为编译时多态(静态多态)和运⾏时多态(动态多态)&#xff0c;这⾥我们重点讲运⾏时多态。 编译时多态(静态多态)主…

车机中 Android Audio 音频常见问题分析方法实践小结

文章目录 前言1. 无声2. 断音3. 杂音4. 延迟播放5. 焦点问题6. 无声问题(连上 BT )其他完善中…… 前言 本文主要总结了一下车机开发中遇到的 Audio 有关的问题&#xff0c;同时参考网上的一案例&#xff0c;由于Audio 模块出现音频问题的场景很多&#xff0c;对每一个出现的问…

气压测试实验(用IIC)

I2C: 如果没有I2c这类总线&#xff0c;连接方法可能会如下图&#xff1a; 单片机所有的通讯协议&#xff0c;无非是建立在引脚&#xff08;高低电平的变换高低电平持续的时间&#xff09;这二者的组合上&#xff0c;i2c 多了一个clock线&#xff0c;负责为数据传输打节拍。 (i2…

linux-L3-linux 复制文件

linux 中要将文件file1.txt复制到目录dir中&#xff0c;可以使用以下命令 cp file1.txt dir/复制文件 cp /path/to/source/file /path/to/destination移动 mv /path/to/source/file /path/to/destination复制文件夹内的文件 cp -a /path/to/source/file /path/to/destinati…

【刷题】Day3--错误的集合

hello&#xff01;又见面啦~~~ 一道习题&#xff0c;要长脑子了...... 【. - 力扣&#xff08;LeetCode&#xff09;】 【思路】 /*** Note: The returned array must be malloced, assume caller calls free().*/void Bubble_sort(int arr[], int size) {int temp;for (int i…

校园安全无小事,EasyCVR视频综合管理平台助力智慧校园视频监控系统全面升级

随着信息技术的飞速发展&#xff0c;智慧校园作为教育信息化的重要载体&#xff0c;正逐步成为提升校园安全管理、优化教育资源配置、增强师生互动体验的关键手段。其中&#xff0c;高效、智能的视频监控系统作为智慧校园不可或缺的一部分&#xff0c;扮演着至关重要的角色。TS…

视频推拉流/直播点播EasyDSS平台安装失败并报错“install mediaserver error”是什么原因?

TSINGSEE青犀视频推拉流/直播点播EasyDSS平台支持音视频采集、视频推拉流、播放H.265编码视频、存储、分发等视频能力服务&#xff0c;在应用场景中可实现视频直播、点播、转码、管理、录像、检索、时移回看等。此外&#xff0c;平台还支持用户自行上传视频文件&#xff0c;也可…

《OpenCV计算机视觉》—— 图像金字塔

文章目录 什么是图像金字塔&#xff1f;一、定义与基本原理二、主要类型三、构建过程四、应用领域 图像金字塔中的下采样和上采样一、下采样&#xff08;Downsampling&#xff09;二、上采样&#xff08;Upsampling&#xff09;三、总结 代码实现 什么是图像金字塔&#xff1f;…

linux---压缩打包

linux打包和压缩文件和目录&#xff1a; 归档(打包)命令&#xff1a;tar 归档就是将多个文件或者目录打包成为一个文件&#xff0c;存放再磁盘中&#xff0c;方便文件或者目录丢失时&#xff0c;可以恢复。 归档文件名使用相对路径 &#xff08;注意区分归档文件和被归档文…

一家电子元件企业终止,业绩规模小,疑似通过收购调节收入利润

贝特电子终止原因如下&#xff1a;首先&#xff0c;报告期内贝特电子营收较低&#xff0c;收购东莞博钺股权可能构成重大资产重组&#xff0c;且假如扣除报告期内来自东莞博钺的净利润&#xff0c;贝特电子的净利润恐怕不符合深交所上市标准&#xff1b;其次&#xff0c;交易所…

QT之QML学习五:添加自定义Qml组件,以及组件管理

开发环境: 1、Qt 6.7.2 2、Pyside6 3、Python 3.11.4 4、Windows 10 重要的事情说三遍,使用自定义qml参考链接: Qt官网参考网址!!! 重要的事情说三遍,使用自定义qml参考链接: Qt官网参考网址!!! 重要的事情说三遍,使用自定义qml参考链接: Qt官网参考网址!!!…

第四天旅游线路预览——从换乘中心到喀纳斯湖

第四天&#xff1a;从贾登峪到喀纳斯风景区入口&#xff0c;晚上住宿贾登峪&#xff1b; 换乘中心有4 路车&#xff0c;喀纳斯①号车&#xff0c;去喀纳斯湖&#xff0c;路程时长约5分钟&#xff1b; 将上面的的行程安排进行动态展示&#xff0c;具体步骤见”Google earth stu…

List<Map<String, Object>>汇总统计排序

开发环境&#xff1a;jdk 1.8 需求一&#xff1a; 1、统计每个小时(升序)不同事件的产品产量 2、统计不同事件&#xff08;OK 、NG&#xff09;的总产量 public static void main(String[] args) {//数据源List<Map<String, Object>> list new ArrayList<Map…

使用 PyCharm 新建 Python 项目详解

使用 PyCharm 新建 Python 项目详解 文章目录 使用 PyCharm 新建 Python 项目详解一 新建 Python 项目二 配置环境1 项目存放目录2 Python Interpreter 选择3 创建隔离环境4 选择你的 Python 版本5 选择 Conda executable 三 New Window 打开项目四 目录结构五 程序编写运行六 …