学历教育网站建设,哪里有免费的个人简历模板,好友介绍网站怎么做,dw班级网站建设文章目录#x1f680;一、堆的原理精讲⛳#xff08;一#xff09;堆的概念⛳#xff08;二#xff09;看图识最大堆⛳#xff08;三#xff09;详解堆是用数组表示的树#x1f680;二、堆的向下调整算法#x1f680;三、堆的向上调整算法#x1f680;四、将任意一棵…
文章目录一、堆的原理精讲⛳一堆的概念⛳二看图识最大堆⛳三详解堆是用数组表示的树二、堆的向下调整算法三、堆的向上调整算法四、将任意一棵树建成堆五、堆的算法实现1.堆的结构体定义2.初始化堆3.判断堆是否为空4.插入新元素5.堆顶元素出列删除元素同时获取堆顶数据6.遍历打印堆7.销毁堆六、拓展⛳一用最大堆或最小堆来实现优先队列⛳二堆排序算法⛳三top - k问题一、堆的原理精讲
⛳一堆的概念 堆Heap一种有特殊用途的数据结构——用来在一组变化频繁发生增删查改的频率较高的数据集中查找最值
堆中某个节点的值总是不大于或不小于其父节点的值;堆总是一棵完全二叉树。每个节点最多可以有两个节点根结点的键值是所有堆结点键值中最大小者且每个结点的值都比其孩子的值大小这样的堆叫最大小堆除了根节点没有兄弟节点最后一个左子节点可以没有兄弟节点其他节点必须有兄弟节点这里需要注意的是在多个子树中并不是说其中一个子树的父结点一定大于另一个子树的儿子结点。
实际上先弄懂树这种数据结构再来看堆就会简单很多了堆是你见过的最有个性的树它是用数组表示的树。所以逻辑结构上其实是一棵树物理结构上是一维数组属于非线性结构 本篇博客默认你没有事先学过树通俗易懂讲解知识详细即使不知道完全二叉树也能辨认出堆即使没学过树也能搞懂堆本篇以最大堆进行讲解 ⛳二看图识最大堆 图1因为93 87而且82无左子节点却有右子节点不满足除了根节点和最后一个左子节点可以没有兄弟节点其他节点必须要有兄弟节点的规定所以图1不是堆
图282是最后一个左子节点但92不是而且没有兄弟节点所以图2也不是堆
图3满足条件为最大堆
⛳三详解堆是用数组表示的树 i为下标由上图我们能看出规律
i的左子节点2i1i的右子节点2i2i的父节点(i-1)/2
这也就是我们在代码实现的时候需要注意的地方
二、堆的向下调整算法
向下调整是让调整的结点与其孩子节点进行比较若想将其调整为小堆那么根结点的左右子树必须都为小堆 若想将其调整为大堆那么根结点的左右子树必须都为大堆有些文章说单纯满足为堆就行这种说法是不对的 向下调整算法的基本思想大部分搜到的都是以最小堆为例我就继续以最大堆为例了
从根结点处开始选出左右孩子中值较大的孩子。让大的孩子与其父亲进行比较。若大的孩子比父亲还大则该孩子与其父亲的位置进行交换。并将原来大的孩子的位置当成父亲继续向下进行调整直到调整到叶子结点为止。若大的孩子比父亲小则不需处理了调整完成整个树已经是大堆了。
代码实现
/*向下调整将当前的节点和子节点调整成最大堆*/
void adjustDown(Heap heap, int index) { int curheap.arr[index];//当前待调整的节点int parent,child;
/*判断否存在大于当前节点子节点如果不存在 则堆本身是平衡的不需要调整如果存在则将最大的子节点与之交换交换后如果这个子节点还有子节点则要继续按照同样的步骤对这个子节点进行调整*/for(parentindex; (parent*21)heap.size; parentchild) {childparent*21;//取两个子节点中的最大的节点if(((child1)heap.size)(heap.arr[child]heap.arr[child1])) {child;}//判断最大的节点是否大于当前的父节点if(curheap.arr[child]) {//不大于则不需要调整跳出循环break;}else {//大于当前的父节点进行交换然后从子节点位置继续向下调整heap.arr[parent]heap.arr[child];heap.arr[child]cur;}}
}三、堆的向上调整算法
向上调整是让调整的结点与其父亲结点进行比较当我们已经有一个堆我们需要在堆的末尾插入数据再对其进行调整使其任然保持堆的结构这里我们就需要用到堆的向上调整算法 向上调整算法的基本思想
将目标结点与其父结点比较若目标结点的值比其父结点的值大则交换目标结点与其父结点的位置将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大则停止向上调整此时该树已经是大堆了。
代码实现
/*将当前的节点和父节点调整成最大堆*/
void adjustUp(Heap heap, int index) {if(index0 || index heap.size) {//大于堆的最大值直接 returnreturn;}while(index0){ int temp heap.arr[index];int parent (index - 1) / 2;if(parent 0){//如果索引没有出界就执行想要的操作if(temp heap.arr[parent]){heap.arr[index] heap.arr[parent];heap.arr[parent] temp;index parent;} else {//如果已经比父亲小 直接结束循环break;}} else {//越界结束循环break;}}
}四、将任意一棵树建成堆
前面我们已经知道堆的向下调整算法是在基于根节点左右子树已经为最大堆或最小堆的前提下才能操作的而堆的向上调整算法是在我们已经建好了一个最大堆或最小堆用于插入元素后的调整
那么如何将任意一棵树建成最大小堆呢这里我就改为如何在数组中快速创建堆
我们把向下调整算法倒着来我们知道满足堆必须左右子树都是大堆或者小堆我们可以利用这个思想从下往上倒着走从第一个非叶子节点开始通过数组下标的控制把它当做根去向下调整依次往上直到把当前路径调整成符合条件的大堆或者小堆即可
还是以最大堆为例讲解可以看到根节点右子树不是一个最大堆所以不能直接用向下调整算法 首先我们需要找到最后一个结点的父结点如图a我们找到的结点是 87然后找出该结点的最大子节点与自己比较若该子节点比自身大则将两个结点交换.。图(a)中87 比左子节点 95 小,则交换之.如图b所示 我们移动到前一个父结点 93,如图©所示。同理做第一步的比较操作,结果不需要交换 继续移动结点到前一个父结点 8282 小于右子节点 95则 82 与 95 交换如图(d)所示82 交换后其值小于左子节点不符合最大堆的特点故需要继续向下调整如图(e)所示 所有节点交换完毕,最大堆构建完成 五、堆的算法实现
1.堆的结构体定义
#define DEFAULT_CAPCITY 128typedef struct _Heap{int *arr; //存储堆元素的数组int size; //当前已存储的元素个数int capacity; //当前存储的容量
}Heap;2.初始化堆
/*初始化堆*/
bool initHeap(Heap heap, int *orginal, int size){//orginal原数据 size数据个数 heap堆int capacity DEFAULT_CAPCITYsize? DEFAULT_CAPCITY:size;heap.arr new int[capacity]; //分配堆中数组空间if(!heap.arr) return false;heap.capacity capacity;heap.size 0;//如果存在原始数据则构建堆if(size0){memcpy(heap.arr, orginal, size*sizeof(int));heap.size size;buildHeap(heap);} else {heap.size 0;}
return true;
}/* 从最后一个父节点(size/2-1 的位置)逐个往前调整所有父节点直到根节点,确保每一个父节点都是一个最大堆最后整体上形成一个最大堆 */
void buildHeap(Heap heap){int i;for(iheap.size/2-1; i0; i--){adjustDown(heap, i);}
}解释
初始化堆操作即为之前讲的将任意一棵树建成堆orginal为函数外传入的原数据然后通过初始化将其建成堆buildHeap即为以最后一个非叶子节点开始的向下调整算法
3.判断堆是否为空
/*判断堆是否为空*/
bool isEmpty(Heap heap){if(heap.size1) return true;return false;
}4.插入新元素
/*最大堆尾部插入节点同时保证最大堆的特性*/
bool insert(Heap heap, int value) {if (heap.size heap.capacity) {fprintf(stderr, 栈空间耗尽\n);return false;}int index heap.size;heap.arr[heap.size] value;adjustUp(heap, index);return true;
}5.堆顶元素出列删除元素同时获取堆顶数据
如果我们将堆顶的元素删除那么顶部有一个空的节点怎么处理
我们先将堆顶的数据与最后一个数据交换位置删除最后一个结点然后再修复堆属性。
原因我们若是直接删除堆顶的数据那么原堆后面数据的父子关系就全部打乱了需要全体重新建堆时间复杂度为ON。若是用上述方法那么只需要对堆进行一次向下调整即可因为此时根结点的左右子树都是大堆我们只需要在根结点处进行一次向下调整即可时间复杂度为O ( log ( N ) 代码实现
/* 删除堆顶元素获取堆顶的数据*/
bool pop(PriorityQueue pq, DataType value) {if (isEmpty(pq)) return false;value pq.arr[0];pq.arr[0] pq.arr[--pq.size];//heap.arr[0] heap.arr[heap.size-1];//heap.size--;adjustDown(pq, 0);// 向下执行堆调整return true;
}6.遍历打印堆
打印堆中的数据这里用了两种打印格式。第一种打印格式是按照堆的物理结构进行打印即打印为一排连续的数字。第二种打印格式是按照堆的逻辑结构进行打印即打印成树形结构。
//求结点数为n的二叉树的深度
int depth(int n) {assert(n 0);if (n0) {int m 2;int hight 1;while (m n 1) {m * 2;hight;}return hight;} else {return 0;}
}//打印堆
void HeapPrint(Heap* php) {assert(php);//按照物理结构进行打印int i 0;for (i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);//按照树形结构进行打印int h depth(php-size);int N (int)pow(2, h) - 1;//与该二叉树深度相同的满二叉树的结点总数int space N - 1;//记录每一行前面的空格数int row 1;//当前打印的行数int pos 0;//待打印数据的下标while (1) {//打印前面的空格int i 0;for (i 0; i space; i) {printf( );}//打印数据和间距int count (int)pow(2, row - 1);//每一行的数字个数while (count--)//打印一行{printf(%02d, php-a[pos]);//打印数据if (pos php-size)//数据打印完毕{printf(\n);return;}int distance (space 1) * 2;//两个数之间的空格数while (distance--)//打印两个数之间的空格{printf( );}}printf(\n);row;space space / 2 - 1;}
}
7.销毁堆
/*销毁堆*/
void destroy(Heap heap){if(heap.arr) delete[] heap.arr;heap-arr NULL;//及时置空heap-size 0;//元素个数置0heap-capacity 0;//容量置0
}六、拓展
⛳一用最大堆或最小堆来实现优先队列
操作系统内核作业调度是优先队列的一个应用实例它根据优先级的高低而不是先到先服务的方式来进行调度 如果最小键值元素拥有最高的优先级那么这种优先队列叫作升序优先队列即总是先删除最小的元素类似的如果最大键值元素拥有最高的优先级那么这种优先队列叫作降序优先队列即总是先删除最大的元素由于这两种类型是完全对称的所以只需要关注其中一种如升序优先队列
⛳二堆排序算法
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素.
(选择排序工作原理 - 第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾。以此类推直到全部待排序的数据元素的个数为零)
/* 实现堆排序 */
void heapSort(Heap heap){if (heap.size1) return ;while(heap.size0){int tmp heap.arr[0];heap.arr[0] heap.arr[heap.size-1];heap.arr[heap.size-1] tmp;heap.size--;adjustDown(heap, 0);// 向下执行堆调整}
}⛳三top - k问题
若要从N个数字中取得最小的K个数字则需要创建大小为K的大堆来获取。若要从N个数字中取得最大的K个数字则需要创建大小为K的小堆来获取。
拜托面试别再问我TopK了_架构师之路-CSDN博客
