做机电预算的网站,长沙网站建设招聘,域名访问wordpress,减粘装置文章目录 前言1.堆的相关概念1.1堆的概念1.2堆的分类1.2.1小根堆1.2.2大根堆 1.3堆的特点堆的实用场景 2.堆的实现2.1初始化2.2插入2.3堆的向上调整2.4删除2.5堆的向下调整2.6判空2.7获取堆顶元素2.8销毁 3.堆排序3.1实现3.2堆排序的时间复杂度问题 前言
在上一篇文章中#… 文章目录 前言1.堆的相关概念1.1堆的概念1.2堆的分类1.2.1小根堆1.2.2大根堆 1.3堆的特点堆的实用场景 2.堆的实现2.1初始化2.2插入2.3堆的向上调整2.4删除2.5堆的向下调整2.6判空2.7获取堆顶元素2.8销毁 3.堆排序3.1实现3.2堆排序的时间复杂度问题 前言
在上一篇文章中我们已经了解了树和二叉树的概念而下面我们要学习的堆在二叉树中非常重要 如果的二叉树还不太了解的大家可以参考作者的上一篇文章 详解二叉树 1.堆的相关概念
1.1堆的概念 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事 一个是数据结构一个是操作系统中管理内存的一块区域分段 1.2堆的分类 对于堆我们可以分成两种 大堆和小堆 1.2.1小根堆 1.小堆 在小堆中堆中的某个节点的值总是不小于其父节点的值换句话说就是父节点的值永远不大于其子节点而如果有两个子节点时子节点之间不存在大小限制关系即指在逻辑上的二叉树结构中根结点子结点总是最大的并且在堆的每一个局部都是如此。例如{1,2,3}可以看作为小根堆而{1,3,2}亦可以看作为小根堆。小根堆的根结点在整个堆中是最小的元素。 1.2.2大根堆 2.大堆 在大堆中堆中的某个节点的值总是不大于其父节点的值换句话说就是父节点的值永远不小于其子节点而如果有两个子节点时子节点之间不存在大小限制关系即指在逻辑上的二叉树结构中根结点子结点总是最大的并且在堆的每一个局部都是如此。例如{3,1,2}可以看作为大根堆而{3,2,1}亦可以看作为大根堆。大根堆的根结点在整个堆中是最大的元素。 详情请看下图 1.3堆的特点 对于二叉树来说我们用堆来实现那为什么不用数组来实现呢 因为对于普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树也就是堆更适合使用顺序结构存储。 并且堆还具有以下的特点让它更加高效和适用 1.维护有序性 最大堆每个节点的值都大于或等于其子节点的值堆顶元素始终是最大值。 最小堆每个节点的值都小于或等于其子节点的值堆顶元素始终是最小值。 这种特性使得堆在需要频繁查找最大或最小元素的场景如优先队列中极为高效无需遍历整个数组即可快速获得。 2.动态调整 堆支持插入和删除元素的同时能够高效地通常是O(log n)时间复杂度重新调整结构以维持其特性这一点在使用数组时难以直接高效实现。 3.内存利用率 实际实现时堆可以采用数组来存储虽然逻辑上是树状结构但实际上占用的是连续内存空间因此内存使用相对高效。 4.排序应用 堆可以作为实现堆排序的基础这是一种不稳定的排序算法其优势在于能够提供较好的最坏情况和平均时间复杂度O(n log n)并且不需要像快速排序那样依赖于数据的初始分布。 堆的实用场景 1、我们可以利用堆的性质来找出一个序列中最大/小的元素尽管通过遍历来解决这一问题可能更好。 2、堆排序堆排序即利用堆的思想来进行排序总共分为两个步骤 1.建堆 升序建大堆 降序建小堆 2.利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 3、建立优先级队列根据上述的小结可知若利用堆来建立优先级队列可以快速的获取到队列中优先级最高/低的任务。 4、n个元素中排列出前k大的元素问题对于此类问题可以建立一个小根堆依次读入n个元素并调整并在堆的规模达到k1时剔除掉第1个元素剩下k个较大元素保持堆的规模不超过k一直循环即可得到最终的结果。 2.堆的实现
实现堆首先要知道堆在结构体中的结构是怎样的//堆的结构
typedef int HeapTypeData;
typedef struct heap
{HeapTypeData* a;int size;int capacity;
}HP;
还有我们要实现的一些接口//初始化
void HPInit(HP* php);
//插入
void HPPush(HP* php, HeapTypeData x);
//删除
void HPPop(HP* php);
//判空
bool HPEmpty(HP* php);
//获取堆顶
HeapTypeData HPTop(HP* php);
//销毁
void HPDestory(HP* php);
//向上调整
void AdjustUp(HeapTypeData* a, int n, int parent);
//向下调整
void AdjustDown(HeapTypeData* a, int child);
//交换
void Swap(HeapTypeData* p1, HeapTypeData* p2);下面我们就来一一实现
2.1初始化
初始化的过程和顺序表的相似void HPInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}2.2插入 1.,由于我们是用堆实现的二叉树的顺序结构在存储结构上还是数组所以当我们插入时要进行扩容 2.当我们在尾端插入一个元素时堆所满足的大根堆或小根堆的条件可能会被违背所以我们还要再创建一个调整函数AdjustUp将数据进行调整那么既然要调整就还需要一个 交换函数swap将数据进行交换 void HPPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, newcapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail);return;}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}2.3堆的向上调整 1.计算父节点位置首先创建孩子节点下标的索引child将最后一个叶子节点数据也就是我们插入的数据的下标计算出其父节点的索引parent公式为(child - 1) / 2 2.循环比较并交换进入一个循环在循环中不断比较当前孩子节点和其父节点的值。如果孩子节点的值小于父节点的值对于x小根堆而言则交换这两个节点的值。这是因为小根堆要求父节点的值不大于子节点的值 3.更新索引并继续在交换之后原来的子节点变成了新的父节点因此需要更新child为parent同时基于新的child计算新的parent继续进行比较和可能的交换直到孩子节点不再小于其父节点或者到达了堆的根部即child 0时 4.退出循环一旦发现孩子节点不小于其父节点或者已经没有父节点可比较即到达了树的根循环结束此时堆的性质已经得到恢复 注意1.这里我们创建的childparent所指向的都是节点的下标
2.这里我们使用小根堆来进行示范当调整大根堆时只需要将循环中if语句的判断符号改为大于号就可以了void AdjustUp(HPDataType* a, int child)
{// 初始条件// 中间过程// 结束条件int parent (child - 1) / 2;//while (parent 0)错误while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}2.4删除 删除我们也要考虑堆的性质问题——是否成立 所以这里也需要判断并进行调整而删除时由于删除的时堆顶的数据所以我们要有一个向下调整的函数来调整整个堆那么我们删除的逻辑就是 1.将堆顶的元素和堆尾的元素进行交换这样删除时更加简单只需要将size–就可以了 2.我们再把交换到堆顶的元素进行调整使之满足堆的成立条件这里我们还是用小根堆进行示范 void HPPop(HP* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size-1]);php-size--;AdjustDown(php-a, php-size, 0);
}
2.5堆的向下调整 1.初始化子节点位置首先创建出计算出当前父节点的左孩子的索引child公式为parent * 2 1。 2.循环比较并交换进入循环只要child的值小于n表示还有子节点可以比较。 … 1.选择较小的子节点如果右孩子存在即child 1 n且右孩子的值小于左孩子的值则将child更新为右孩子的索引因为我们要找到两个子节点中更小的那个。 … 2.比较并交换如果找到的子节点child的值小于其父节点parent的值说明违反了最小堆的性质这时需要交换它们的值并将当前的child位置作为新的父节点位置继续向下比较。 … 3.更新位置交换后原child位置已成为新的父节点位置因此更新parent child并基于新的父节点重新计算其左孩子的索引child parent * 2 1继续循环。 … 4.退出条件如果子节点不小于父节点或者已经没有更多的子节点可比较即child n则跳出循环。 3.结束循环结束后堆的性质得到了恢复即以parent为根的子树满足最小堆的定义。 void AdjustDown(HPDataType* a, int n, int parent)
{// 先假设左孩子小int child parent * 2 1;while (child n) // 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;}}
}
2.6判空
bool HPEmpty(HP* php)
{assert(php);return php-size 0;
}2.7获取堆顶元素
HPDataType HPTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}2.8销毁 销毁时要注意一一销毁并且把变量置为零 void HPDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}3.堆排序
3.1实现 堆排序首先要建堆建堆时 1.升序建大堆 2.降序建小堆 而对于这两种建堆方式我们选择用第二种因为我们从时间复杂度的角度去对比时会发现 1.建大堆的时间复杂度为O(N*logN); 2.建小堆的则为O(N); 所以我们选择第二种 1.建堆: 我们从最后一个非叶节点开始逆序遍历至根节点的方式来构建最小堆。这样做的目的是直接通过向上调整函数递归调整每个子树为最小堆最终整个数组构成一个最小堆。计算最后一个非叶节点的索引公式为(sz-1-1)/2然后从这个索引开始逐步向前执行向上调整操作。 (sz-1-1)/2sz-1-最后一个元素sz-1-1/2找到父节点 2.排序: 首先将堆顶元素数组中的最小值与数组末尾元素交换确保当前最小值位于正确的位置即数组末尾。 然后因为堆顶元素现在是数组的末尾元素已经正确排序所以缩小堆的有效大小end - 1并在剩下的元素中再次调用向上调整函数调整剩余元素为最小堆。这个过程重复直到整个数组都被正确排序。 void HeapSort(int* a, int n)
{// 降序建小堆// 升序建大堆// 向上调整建堆 O(N*logN)/*for (int i 1; i n; i){AdjustUp(a, i);}*/// 向下调整建堆 O(N)for (int i (n-1-1)/2; i 0; i--){AdjustDown(a, n, i);}// O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}
3.2堆排序的时间复杂度问题
我们通过两张图来理解最后得出结果为O(N*logN)
