万网app下载,seo插件wordpress,网校网站怎么做,中国500强企业前言 本文将详细讲解堆。堆是一种二叉树#xff08;一般是完全二叉树#xff09;使用顺序结构的数组来存储。 tip#xff1a;这里我们需要注意区分堆在不同地方的含义#xff0c;这里的堆是一个数据结构#xff0c;操作系统虚拟进程地址空间的堆是操作系统中管理内存的一块…前言 本文将详细讲解堆。堆是一种二叉树一般是完全二叉树使用顺序结构的数组来存储。 tip这里我们需要注意区分堆在不同地方的含义这里的堆是一个数据结构操作系统虚拟进程地址空间的堆是操作系统中管理内存的一块区域分段。 一、堆的概念及结构
1、堆的概念
如果有一个关键码的集合K把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足堆中某个节点的值总是不大于或不小于其父节点的值则称为大堆小堆。 将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 tip
堆总是一颗完全二叉树。大堆树中所有父亲都大于或等于孩子。小堆树中所有父亲都小于或等于孩子。注意堆不一定是有序的因为左右孩子谁大谁小并没有限制。
2、堆的结构 tip学习堆我们一定要画图因为堆在内存中的存储结构是一个数组但元素之间的逻辑是一颗二叉树我们很难可以将其想象出来所以学堆画图很重要
二、堆的实现
虽然堆分为两类大根堆和小根堆但是他们的结构与功能都是类似的所以这里我们实现一个大堆为例就可以了。 我们先预览堆的结构与所需的接口函数
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//堆——完全二叉树
//虽然堆在内存上是用一段物理地址连续的存储单元依次存储的但是逻辑关系上是一颗完全二叉树
//堆又分为大根堆和小根堆
//大根堆树中所有父亲都大于或等于孩子
//小根堆树中所有父亲都小于或等于孩子
//大根堆和小根堆的实现基本相似所以这里我们以实现一个大根堆为例typedef int HPDataType;//重命名堆中数据的类型——》优点①一改全改②见名知意
typedef struct Heap
{HPDataType* arr;//指向堆区申请的数组int size;//存储有效数据个数int capacity;//堆的容量空间
}HP;//堆的初始化——初始化堆的成员变量
void HeapInit(HP* php);//堆的销毁——动态申请的空间自己要记得销毁否则可能造成内存泄漏
void HeapDestroy(HP* php);//交换
void Swap(HPDataType* e1, HPDataType* e2);//堆的向上调整
void AdjustUp(HPDataType* arr, int child);//堆的插入
void HeapPush(HP* php, HPDataType x);//打印堆数组
void HeapPrint(HP* php);//判断堆是否为空
bool HeapIsEmpty(HP* php);//堆的向下调整
void AdjustDown(HPDataType* arr, int n, int parent);//堆的删除
void HeapPop(HP* php);//获取堆顶元素
HPDataType HeapTop(HP* php);//获取堆的有效元素个数
int HeapSize(HP* php);1、堆的结构
堆由三个成员变量组成分别是arr指针指向动态申请的数组、size存储堆的有效数据个数、capacity存储堆的容量所以堆是一个复杂结构我们将其定义为结构体。
typedef int HPDataType;//重命名堆中数据的类型——》优点①一改全改②见名知意
typedef struct Heap
{HPDataType* arr;//指向堆区申请的数组int size;//存储有效数据个数int capacity;//堆的容量空间
}HP;tip
建议将堆中存储的数据的类型typedeftypedef 一可以方便我们更改堆的类型二见名知意。
2、堆的初始化
堆的初始化模块功能初始化堆对象的三个成员变量
//堆的初始化——初始化堆的成员变量
void HeapInit(HP* php)
{//断言指针的有效性php不可能为空assert(php);//初始化堆的成员php-arr (HPDataType*)malloc(sizeof(HPDataType) * 4);if (NULL php-arr){//扩容失败perror(HeapInit::malloc);return;}php-size 0;php-capacity 4;
}
3、堆的销毁
堆的销毁模块功能清理堆对象使用的资源并销毁堆对象中动态申请的资源。
//堆的销毁——动态申请的空间自己要记得销毁否则可能造成内存泄漏
void HeapDestroy(HP* php)
{assert(php);//释放堆对象申请的动态空间free(php-arr);//free之后php-arr仍指向原来的空间可能造成非法访问或多次释放建议置为空php-arr NULL;php-size 0;php-capacity 0;
}4、堆的插入(重点)
堆的插入模块功能先在数组尾插入数据数据再向上调整找到自己在大堆中的位置。 问题1 堆插入为什么只有一种 因为堆要满足大根堆或小根堆的性质头插和任意位置插入会改变堆原本的结构而尾插不会改变堆原本的结构。 问题2 已知有一个数组它是按照大根堆的性质存储的。现在我们在数组尾插入一个数据80仍想让数组按照大根堆存储该怎么实现 使用向上调整算法实现。向上调整算法的思想 将目标节点孩子结点与其父节点比较。如果目标节点大于其父节点交换两个节点的值并继续向上比较。结束向上比较的条件①如果目标节点小于其父节点则停止向上比较②最坏的情况是向上比较到根才结束。 因为其过程是不断的向上比较所以将其叫做向上调整算法。 tip向上调整的前提是除了目标位置前面数据构成大堆/小堆。 1交换两个数据
因为在堆中许多地方都会交换两个数据所以我们将其模块化。
//交换——有多个模块需要交换所以将其模块化
void Swap(HPDataType* e1, HPDataType* e2)
{HPDataType temp *e1;*e1 *e2;*e2 temp;
}tip
注意值传递不会改变形参的改变不会改变实参。
2向上调整
注意向上调整的前提是除了目标位置前面数据构成大堆/小堆。
//堆的向上调整
void AdjustUp(HPDataType* arr, int child)
{//存储父亲的下标int parent (child - 1) / 2;//大堆向上调整当孩子大于父亲时孩子与父亲交换//向上调整的结束条件//①最坏情况向上到根才结束即child 0(parent0)。但注意不能用parent 0作为结束因为parent (child - 1) / 2不可能小于0.//②特殊情况当孩子不大于父亲时结束。while (child 0){if (arr[child] arr[parent]){//交换Swap(arr[child], arr[parent]);//继续向上调整child parent;parent (child - 1) / 2;}else{//跳出循环break;}}
}tip
最坏情况是到根结束注意不能用parent 0来判断因为parent child - 1/ 2不可能小于0。小根堆的向上调整与大根堆类似只需将if中的arr[child] arr[parent]改成arr[child] arr[parent]即可。
3堆的插入
//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//1、向堆插入数据要先判断是否扩容if (php-size php-capacity){//扩容//realloc可能扩容失败所以先使用一个临时变量保存realloc的返回值HPDataType* temp (HPDataType*)realloc(php-arr, sizeof(HPDataType) * php-capacity * 2);//判断是否扩容成功if (temp ! NULL){//扩容成功仍然使用php-arr指向申请的空间并将temp置为空php-arr temp;temp NULL;//注意别忘记更新容量php-capacity * 2;}else{perror(realloc);return;}}//2、堆的插入——先在数组尾插入数据再向上调整//①数组尾插——不需要挪动时间复杂度O(1)php-arr[php-size] x;php-size;//②向上调整AdjustUp(php-arr, php-size - 1);
}tip
注意我们插入数据之前要检查是否需要扩容。
5、堆的判空
堆的判空模块功能如果堆为空则返回真反之返回假。
//判断堆是否为空
bool HeapIsEmpty(HP* php)
{assert(php);//当堆中有效个数为0时堆为空return 0 php-size;
}tip
判断一个变量与一个常量是否相等时建议变量做右操作数提高代码的健壮性。
6、堆的删除(重点)
堆的删除模块功能删除堆顶的元素。 问题1 堆的删除为什么只能删除堆顶元素 因为堆的性质堆顶元素的值最大或最小。 所以删除堆顶元素才有意义删除掉最大的之后我们可以继续选出第二大的。 问题2 我们直接删除堆顶 我们不会直接删除堆顶元素因为直接删除堆顶元素有两大问题 数组头删需要挪动数据时间复杂度为O(N)效率低。父子兄弟关系全乱了。 问题3 怎样删除堆顶 思路 交换把堆顶元素与最后一个元素交换删除堆顶数组尾删直接size–即可向下调整运用向下调整算法确保堆的结构。 问题4 怎样向下调整 思路 通过假设法选出左右孩子较大的那个孩子结点将较大的那个孩子结点与父节点比较如果比父节点大则交换继续向下比较直到比父节点小才停止最坏的情况是向下比较到叶子才停止。 tip向下调整的前提是左右子树都是大堆/小堆。 1向下调整
注意向下调整的前提是左右子树都是大堆/小堆。
//堆的向下调整
void AdjustDown(HPDataType* arr, int n, int parent)
{//假设法定义一个变量存储较大孩子的下标先假设左孩子大再通过if确定假设是否成立。int child parent * 2 1;//大堆向下调整当父亲小于较大的孩子孩子与父亲交换//向下结束的条件//①最坏情况 向下到叶子结束即child(parent * 2 1) n。//②特殊情况当孩子不小于父亲时结束。while (child n){//if确定假设是否成立//注意要先判断child 1是否为堆有效数据if (child 1 n arr[child] arr[child 1]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);//继续向下调整parent child;child parent * 2 1;}else{break;}}
}
tip
比较左右孩子的时候需要先判断右孩子是否为堆的有效数据当child(parent * 2 1) n没有右孩子。小根堆的向下调整与大根堆类似只需将if中的arr[child] arr[parent]改成arr[child] arr[parent]即可。
2堆的删除
//堆的删除
void HeapPop(HP* php)
{assert(php);//删除堆不能为空assert(!HeapIsEmpty(php));//堆只有删除堆顶元素才有意义//问题是直接删吗//答案是不是直接删有两个问题——①效率低挪动数据时间复杂度O(N)②堆的父子兄弟关系全乱了//①交换堆顶与堆尾Swap(php-arr[0], php-arr[php-size - 1]);//②数组尾删php-size--;//③向下调整AdjustDown(php-arr, php-size, 0);
}tip
在删除数据之前需要判断堆是否为空。堆删除的思路口诀一交换二删除三向下调整。
7、获取堆顶元素
//获取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);//断言堆不为空assert(!HeapIsEmpty(php));return php-arr[0];
}tip
为了程序的健壮性在获取之前断言堆不为空。获取堆顶元素直接返回数组下标为0的元素即可
8、获取堆的有效数据个数
//获取堆的有效元素个数
int HeapSize(HP* php)
{assert(php);return php-size;
}tip
直接返回size即可。
9、堆的打印
//打印堆数组
void HeapPrint(HP* php)
{assert(php);int i 0;for (i 0; i php-size; i){printf(%d , php-arr[i]);}printf(\n);
}tip
堆在内存中是连续存储的其本质就是数组所以使用for循环就打印了。
三、总代码
1、接口声明模块
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//堆——完全二叉树
//虽然堆在内存上是用一段物理地址连续的存储单元依次存储的但是逻辑关系上是一颗完全二叉树
//堆又分为大根堆和小根堆
//大根堆树中所有父亲都大于或等于孩子
//小根堆树中所有父亲都小于或等于孩子
//大根堆和小根堆的实现基本相似所以这里我们以实现一个大根堆为例typedef int HPDataType;//重命名堆中数据的类型——》优点①一改全改②见名知意
typedef struct Heap
{HPDataType* arr;//指向堆区申请的数组int size;//存储有效数据个数int capacity;//堆的容量空间
}HP;//堆的初始化——初始化堆的成员变量
void HeapInit(HP* php);//堆的销毁——动态申请的空间自己要记得销毁否则可能造成内存泄漏
void HeapDestroy(HP* php);//交换
void Swap(HPDataType* e1, HPDataType* e2);//堆的向上调整
void AdjustUp(HPDataType* arr, int child);//堆的插入
void HeapPush(HP* php, HPDataType x);//打印堆数组
void HeapPrint(HP* php);//判断堆是否为空
bool HeapIsEmpty(HP* php);//堆的向下调整
void AdjustDown(HPDataType* arr, int n, int parent);//堆的删除
void HeapPop(HP* php);//获取堆顶元素
HPDataType HeapTop(HP* php);//获取堆的有效元素个数
int HeapSize(HP* php);
2、接口实现模块
#includeHeap.h//堆的初始化——初始化堆的成员变量
void HeapInit(HP* php)
{//断言指针的有效性php不可能为空assert(php);//初始化堆的成员php-arr (HPDataType*)malloc(sizeof(HPDataType) * 4);if (NULL php-arr){//扩容失败perror(HeapInit::malloc);return;}php-size 0;php-capacity 4;
}//堆的销毁——动态申请的空间自己要记得销毁否则可能造成内存泄漏
void HeapDestroy(HP* php)
{assert(php);//释放堆对象申请的动态空间free(php-arr);//free之后php-arr仍指向原来的空间可能造成非法访问或多次释放建议置为空php-arr NULL;php-size 0;php-capacity 0;
}//交换——有多个模块需要交换所以将其模块化
void Swap(HPDataType* e1, HPDataType* e2)
{HPDataType temp *e1;*e1 *e2;*e2 temp;
}//堆的向上调整
void AdjustUp(HPDataType* arr, int child)
{//存储父亲的下标int parent (child - 1) / 2;//大堆向上调整当孩子大于父亲时孩子与父亲交换//向上调整的结束条件//①最坏情况向上到根才结束即child 0(parent0)。但注意不能用parent 0作为结束因为parent (child - 1) / 2不可能小于0.//②特殊情况当孩子不大于父亲时结束。while (child 0){if (arr[child] arr[parent]){//交换Swap(arr[child], arr[parent]);//继续向上调整child parent;parent (child - 1) / 2;}else{//跳出循环break;}}
}//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//1、向堆插入数据要先判断是否扩容if (php-size php-capacity){//扩容//realloc可能扩容失败所以先使用一个临时变量保存realloc的返回值HPDataType* temp (HPDataType*)realloc(php-arr, sizeof(HPDataType) * php-capacity * 2);//判断是否扩容成功if (temp ! NULL){//扩容成功仍然使用php-arr指向申请的空间并将temp置为空php-arr temp;temp NULL;//注意别忘记更新容量php-capacity * 2;}else{perror(realloc);return;}}//2、堆的插入——先在数组尾插入数据再向上调整//①数组尾插——不需要挪动时间复杂度O(1)php-arr[php-size] x;php-size;//②向上调整AdjustUp(php-arr, php-size - 1);
}//打印堆数组
void HeapPrint(HP* php)
{assert(php);int i 0;for (i 0; i php-size; i){printf(%d , php-arr[i]);}printf(\n);
}//判断堆是否为空
bool HeapIsEmpty(HP* php)
{assert(php);//当堆中有效个数为0时堆为空return 0 php-size;
}//堆的向下调整
void AdjustDown(HPDataType* arr, int n, int parent)
{//假设法定义一个变量存储较大孩子的下标先假设左孩子大再通过if确定假设是否成立。int child parent * 2 1;//大堆向下调整当父亲小于较大的孩子孩子与父亲交换//向下结束的条件//①最坏情况 向下到叶子结束即child(parent * 2 1) n。//②特殊情况当孩子不小于父亲时结束。while (child n){//if确定假设是否成立//注意要先判断child 1是否为堆有效数据if (child 1 n arr[child] arr[child 1]){child;}if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);//继续向下调整parent child;child parent * 2 1;}else{break;}}
}//堆的删除
void HeapPop(HP* php)
{assert(php);//删除堆不能为空assert(!HeapIsEmpty(php));//堆只有删除堆顶元素才有意义//问题是直接删吗//答案是不是直接删有两个问题——①效率低挪动数据时间复杂度O(N)②堆的父子兄弟关系全乱了//①交换堆顶与堆尾Swap(php-arr[0], php-arr[php-size - 1]);//②数组尾删php-size--;//③向下调整AdjustDown(php-arr, php-size, 0);
}//获取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);//断言堆不为空assert(!HeapIsEmpty(php));return php-arr[0];
}//获取堆的有效元素个数
int HeapSize(HP* php)
{assert(php);return php-size;
}
3、功能测试模块
#includeHeap.hint main()
{//定义堆变量HP hp;//初始化HeapInit(hp);//插入数据HeapPush(hp, 6);HeapPush(hp, 16);HeapPush(hp, 36);HeapPush(hp, 56);HeapPush(hp, -1);HeapPush(hp, 5);HeapPush(hp, -16);HeapPush(hp, 35);HeapPush(hp, 19);HeapPush(hp, 9);HeapPush(hp, 6);HeapPush(hp, 18);HeapPrint(hp);//找出前k个大的数int k 0;scanf(%d, k);while (!HeapIsEmpty(hp) k--){printf(%d , HeapTop(hp));//删除HeapPop(hp);}printf(\n);HeapDestroy(hp);return 0;
}运行结果
