数据结构(C):从初识堆到堆排序的实现

2024-06-02 19:20

本文主要是介绍数据结构(C):从初识堆到堆排序的实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

🌞0.前言

🚈 1.堆的概念

🚈 2.堆的实现

🚝2.1堆向下调整算法

🚝2.2堆的创建(堆向下调整算法)

✈️2.2.1 向下调整建堆时间复杂度

🚝2.3堆向上调整算法

🚝2.4堆的创建(堆向上调整算法)

✈️2.4.1向上调整算法建堆的时间复杂度

🚝2.5堆的插入

🚝2.6堆的删除

🚝2.7建堆的代码实现

✈️2.7.1向下调整实现堆的建立

✈️2.7.2向上调整实现堆的建立

🚈 3.完整的堆的代码的实现

🚝3.1堆的创建

🚝3.2堆的销毁

🚝3.3堆的插入

🚝3.4堆的删除(头删)

🚝3.5取堆顶元素的数据

🚝3.6 堆的数据个数

🚝3.7堆的判空

🚈 4.堆的应用堆排序

✍5.结束语


🌞0.前言

        言C之言,聊C之识,以C会友,共向远方。各位博友的各位你们好啊,这里是持续分享数据结构知识的小赵同学,今天要分享的数据结构知识是,在这一章,小赵将会向大家展开聊聊的相关知识。✊

🚈 1.堆的概念

堆就是以 二叉树的顺序存储方式来存储元素,同时又要满足 父亲结点存储数据都要大于等于儿子结点存储数据(也可以是父亲结点数据都要小于等于儿子结点数据)的一种数据结构。堆只有两种即大堆和小堆,大堆就是父亲结点数据大于等于儿子结点数据,小堆则反之。

同时这里要注意的是堆一定是完全二叉树,不然就不是堆。那完全二叉树是什么呢?这个地方不懂的博友可以看我们的这一篇博客:数据结构(C)树的概念和二叉树初见http://t.csdnimg.cn/JnWfb

如果看完了还是不明白可以私信小赵询问哦。

好了下面让我们看看上面说的两种堆在图上是怎么呈现的呢?

 

我们发现我们的任意一个父节点都比他的两个子节点大(或等于)这个时候这就是一个大堆。 

我们发现我们的任意一个父节点都比他的两个子节点小(或等于)这个时候这就是一个小堆。 

虽然堆是完全二叉树,但其的存储方式却与二叉树不同,我们一般存储堆的方式是数组。而我们上面所画的叫逻辑结构,那怎么由数组的存储方式,转化为我们的逻辑结构呢?

我们在介绍二叉树的时候其实也曾简单的说过二叉树是有顺序的,是从上到下,从左向右的,按这个顺序我们就可以给我们的二叉树标序号。 

那么就可以我们的逻辑结构转化成我们的数组结构了,既然我们已经会将逻辑结构转化为数组结构了,那么将数组结构转化为逻辑结构也就没有这么难了,大家可以自己试试,如果实在实现不了也可以找小赵咨询哦。 

🚈 2.堆的实现

🚝2.1堆向下调整算法

什么是向下调整算法呢?其实正如其名就是从上到下调整堆的意思。要想更深入了解这个东西就先来看这张图。

看这张图这是一个很明显的小堆对吧,那我这个时候要你改成一个大堆怎么办,这个时候的操作其实是2,3进行比较,然后拿出大的和1换这个就成大堆了。 

可如果这个时候我给你的是个这样的堆你又该怎么办(要改成小堆)

 其实这个时候也是可以操作的,因为下面是有序的堆,我们只需要按照前面的顺序一步步来就可以完成了。只不过这个时候改成了选择两个子中的小的哪一个,因为我们要做得是小堆(这个时候之所以说他下面是有序的堆是因为盖住最上面的一个,下面的两个堆都是小堆,我们要改成的也是小堆。)

那如果是无序的呢? (改成小堆)

这个时候我们发现我们再想把这个改成小堆的难度就很大了。

🚝2.2堆的创建(堆向下调整算法)

那通过上面的实验我们发现,想通过一个位置来做上面的操作,并把整个堆都变成小(大)堆,必须下面就是一个小(大)堆。所以我们的向下调整其实也是从最下面的开始的,而且我们刚刚做的步骤其实就是向下调整。 

那么再面对上面那个无序的堆我们也就有方法了。

这个时候我们就可以做到将无序的堆转化成有序的堆了。 那么这个时候我们面对任何一个无序的数组,都可以通过这样的方式将他转化成堆.(至少在逻辑图上可以实现,代码实现下面说)

✈️2.2.1 向下调整建堆时间复杂度

每层节点个数 × 最坏情况向下调整次数:
T(N) = 2^(h-2) × 1 + 2^(h-3) × 2 + … … + 2^1 × (h-2)+2^0*(h-1)

错位相减法
等号左右两边乘个 2 得到一个新公式,再用新公式减去旧的公式,具体见下图

🚝2.3堆向上调整算法

聊了向下调整算法,那么其实也有向上调整算法。

如这里我们如何把这个堆改成大堆

向上调整一般是怎么玩的呢,一般我们的向上调整法就是从下面往上调整,向这里要想调整到我们想要的样子就要三步

🚝2.4堆的创建(堆向上调整算法)

这里呢也和上面一样,向上调整的地方的上面必须是已经调整好的,所以我们一般用向上调整法去建堆的时候往往要从第一个开始建堆到最下面。

✈️2.4.1向上调整算法建堆的时间复杂度

T(N) = 2^1× 1 + 2^2× 2 + 2^3 ×3+ … … + 2^(h-3)× (h-3) + 2^(h-2) × (h-2)+ 2^(h-1) × (h-1)

综上:向下调整建堆要更优秀,效率更高

但总的来建堆的时间复杂度是O(N*logN)

🚝2.5堆的插入

像我们一般堆是用数组存储的,我们一般插入也是从数组后面插入,所以也就是在最后一个位置插入,而这个时候上面的堆都是有顺序的,我们可以用我们的向上调整算法来解决堆的插入。

🚝2.6堆的删除

堆的删除,我们一般针对的是头元素的删除,这个时候我们采取的策略是将头元素和尾元素交换,然后让头元素,向下调整(因为下面的堆都已经是有顺序的)

这样就可以完成头删了 

🚝2.7建堆的代码实现

代码的实现我们的表示表示方式和前面的双亲节点是对应的(parent),然后子节点就是(child)

✈️2.7.1向下调整实现堆的建立

//小堆的建立
void Swap(int* a, int* b)//交换
{int tmp = *a;*a = *b;*b = tmp;
}
//小堆
void ADjustDown(int *a,int parent,int n)
{int child = parent * 2 + 1;//子节点和双亲节点的关系while (child < n){if (child + 1 < n && a[child + 1] < a[child])//选出两个孩子中较小的一个{child++;}if (a[child] < a[parent])//若子节点比双亲节点小{Swap(&a[child], &a[parent]);//交换接着向下进行parent = child;child = parent * 2 + 1;}else{break;}}
}
void Heap(int *a,int n)
{int i = (n - 1 - 1) / 2;//找到最后一个双亲节点while (i >= 0){ADjustDown(a, i, n);i--;}
}
int main()
{int a[10] = { 3,5,9,8,6,1,5,2,6,323 };Heap(a, 10);
}

这里的主要方式就是我们前面的图所演示的,就是从最后一个双亲节点向下调整,然后调整过程中要小心不要让字节出了数组的范围,同时要记住子节点和双亲节点的关系。 这样可以方便我们的代码的实现。

✈️2.7.2向上调整实现堆的建立

//建立小堆
void Swap(int* a, int* b)//交换
{int tmp = *a;*a = *b;*b = tmp;
}
void ADjustUp(int*a,int child,int n)
{int parent = (child - 1) / 2;//双亲节点和子节点关系while (parent >= 0){if (a[child] < a[parent])//如果子节点比双亲节点小,那么交换,并且向上移动{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1 - 1) / 2;}else{break;}}
}
void Heap(int* a, int n)
{int i = 0;while (i < n)//从最上面开始建堆{ADjustUp(a, i, n);i++;}
}
int main()
{int a[10] = { 3,5,9,87,6,12,7,11,13,1 };Heap(a, 10);
}

这里也基本上就是我们上面逻辑的实现,向上建堆,就要保证上面都是已经建好的堆,那么就得从首元素开始依次向下,建堆。 

🚈 3.完整的堆的代码的实现

要想实现完整的堆的实现就要实现以下几个函数

typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);

这样我们的堆就可以像之前的链表顺序表等一样使用了。 

🚝3.1堆的创建

和上面的代码逻辑基本一样。

这里我们主要采用的是向下排序建堆,因为向下排序的时间复杂度低。

void HeapCreate(Heap* hp, HPDataType* a, int n)
{hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (hp->_a == NULL){perror("malloc failed");}memcpy(hp->_a, a, n);hp->_capacity = n;hp->_size = n;int i = (n - 1 - 1) / 2;while (i >= 0){ADjustDown(a, i, n);i--;}
}

🚝3.2堆的销毁

void HeapDestory(Heap* hp)
{free(hp->_a);hp->_a = NULL;hp->_capacity = 0;hp->_size = 0;
}

🚝3.3堆的插入

void HeapPush(Heap* hp, HPDataType x)
{if (hp->_size == hp->_capacity){int newcapacity = (hp->_size == 0 ? 4 : hp->_capacity * 2);//如果没有内存就给4,有就是原来内存的双倍HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc failed");exit(-1);//退出程序,返回-1;}hp->_a = tmp;hp->_capacity = newcapacity;}hp->_a[hp->_size] = x;hp->_size++;ADjustUp(hp->_a, hp->_size - 1, hp->_size);//上面都是建好的堆,只需要向上调整即可
}

🚝3.4堆的删除(头删)

void HeapPop(Heap* hp)
{if (!HeapEmpty(hp)){Swap(&(hp->_a[0]), &(hp->_a[hp->_size - 1]));//首尾交换ADjustDown(hp->_a, 0, hp->_size);//向下调整hp->_size--;//删除尾}else{return;}
}

🚝3.5取堆顶元素的数据

HPDataType HeapTop(Heap* hp)
{if (!HeapEmpty(hp))//不是空集,返回首元素(即堆顶元素){return hp->_a[0];}else{return NULL;}
}

🚝3.6 堆的数据个数

int HeapSize(Heap* hp)
{return hp->_size;
}

🚝3.7堆的判空

int HeapEmpty(Heap* hp)
{return hp->_size == 0;//如果等式成立返回非零数,不成立返回零
}

🚈 4.堆的应用堆排序

下面我们进入堆排序的学习,堆排序是我们的排序中比较优的一个排序,他具体是如何实现的呢?其实我们在前面的知识中已经发现了,就是如果我们建的是小堆,那小堆的堆顶元素一定是整个堆里面最小的,大堆的堆顶元素一定是最大的,那么如果我们想排一个顺序的方法就出来了,先把数组弄成一个大堆,再把第一个元素和最后一个元素交换,然后这个时候我们就排好了最大的一个,接着我们不管最后一个元素,对前面的n-1个元素再次建成大堆(其实只要进行向下调整就可以了因为下面的已经是大堆了),再重复上述操作。

那么我们就可以试着用代码实现了。

//建大堆
void ADjustDown(int* a, int parent, int n)
{int child = parent * 2 + 1;//子节点和双亲节点的关系while (child < n){if (child + 1 < n && a[child + 1] > a[child])//选出两个孩子中较大的一个{child++;}if (a[child] > a[parent])//若子节点比双亲节点大{Swap(&a[child], &a[parent]);//交换接着向下进行parent = child;child = parent * 2 + 1;}else{break;}}
}
void Heapsort(int* a, int n)
{int i = (n - 1 - 1) / 2;while (i >= 0){ADjustDown(a, i, n);i--;}//建堆while (n > 0){n--;Swap(&a[0], &a[n]);//交换首尾元素位置ADjustDown(a, 0, n);//下面都是建好的,只要向下调整就可以}
}
int main()
{int a[10] = { 3,5,9,87,6,12,7,11,13,1 };Heapsort(a,10);
}

✍5.结束语

好了小赵今天的分享就到这里了,如果大家有什么不明白的地方可以在小赵的下方留言哦,同时如果小赵的博客中有什么地方不对也希望得到大家的指点,谢谢各位家人们的支持。你们的支持是小赵创作的动力,加油。

如果觉得文章对你有帮助的话,还请点赞,关注,收藏支持小赵,如有不足还请指点,方便小赵及时改正,感谢大家支持!!!

这篇关于数据结构(C):从初识堆到堆排序的实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1024865

相关文章

IDEA如何实现远程断点调试jar包

《IDEA如何实现远程断点调试jar包》:本文主要介绍IDEA如何实现远程断点调试jar包的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录问题步骤总结问题以jar包的形式运行Spring Boot项目时报错,但是在IDEA开发环境javascript下编译

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

python获取cmd环境变量值的实现代码

《python获取cmd环境变量值的实现代码》:本文主要介绍在Python中获取命令行(cmd)环境变量的值,可以使用标准库中的os模块,需要的朋友可以参考下... 前言全局说明在执行py过程中,总要使用到系统环境变量一、说明1.1 环境:Windows 11 家庭版 24H2 26100.4061

Python中bisect_left 函数实现高效插入与有序列表管理

《Python中bisect_left函数实现高效插入与有序列表管理》Python的bisect_left函数通过二分查找高效定位有序列表插入位置,与bisect_right的区别在于处理重复元素时... 目录一、bisect_left 基本介绍1.1 函数定义1.2 核心功能二、bisect_left 与

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

pandas实现数据concat拼接的示例代码

《pandas实现数据concat拼接的示例代码》pandas.concat用于合并DataFrame或Series,本文主要介绍了pandas实现数据concat拼接的示例代码,具有一定的参考价值,... 目录语法示例:使用pandas.concat合并数据默认的concat:参数axis=0,join=

java中BigDecimal里面的subtract函数介绍及实现方法

《java中BigDecimal里面的subtract函数介绍及实现方法》在Java中实现减法操作需要根据数据类型选择不同方法,主要分为数值型减法和字符串减法两种场景,本文给大家介绍java中BigD... 目录Java中BigDecimal里面的subtract函数的意思?一、数值型减法(高精度计算)1.

C#代码实现解析WTGPS和BD数据

《C#代码实现解析WTGPS和BD数据》在现代的导航与定位应用中,准确解析GPS和北斗(BD)等卫星定位数据至关重要,本文将使用C#语言实现解析WTGPS和BD数据,需要的可以了解下... 目录一、代码结构概览1. 核心解析方法2. 位置信息解析3. 经纬度转换方法4. 日期和时间戳解析5. 辅助方法二、L

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

C/C++中OpenCV 矩阵运算的实现

《C/C++中OpenCV矩阵运算的实现》本文主要介绍了C/C++中OpenCV矩阵运算的实现,包括基本算术运算(标量与矩阵)、矩阵乘法、转置、逆矩阵、行列式、迹、范数等操作,感兴趣的可以了解一下... 目录矩阵的创建与初始化创建矩阵访问矩阵元素基本的算术运算 ➕➖✖️➗矩阵与标量运算矩阵与矩阵运算 (逐元