文章目录一. 引言二. 核心概念逻辑树与物理数组的映射1二叉树的存储结构三. 方案的选择普通数组 vs 堆四. 核心功能的逻辑实现1. 堆的结构体定义与物理架构2. 标准初始化与资源销毁3. 稳健入堆动态扩容与向上调整1向上调整法2思考4. 精准出堆堆顶删除与向下调整向下调整法5. 堆顶获取与判空1获堆顶2判空五. 进阶应用与延伸1原地建堆1. 向上调整法原地建堆 ( O(N * log N) )2. 向下调整法原地建堆 ( O(log N) )2TopK问题一.引言在上一篇文章中我们讲到了队列队列讲究的是绝对的公平遵循 FIFOFirst In, First Out先进先出线性原则堆打破了纯粹的时间顺序出队时不看是谁先来的而是看“谁的优先级高/谁的数据最大或最小”。生动比喻像是在车站排队买票先来后到而堆就像是医院的急诊室病情最严重的患者优先级最高哪怕最后进来也会被优先安排治疗。二.核心概念逻辑树与物理数组的映射堆本质是由完全二叉树构成如图在这里我们可以发现树的构成是由众多个节点所连接而成那么我们联系之前所学知识可以想到这种树的连接方式用链表最合适不过了毕竟从图中就可以发现他是相互连接起来的在这里我们就要讲二叉树的两种存储结构。1二叉树的存储结构顺序存储 顺序结构顺序存储就是利用数组来进行数据存储只适合完全二叉树即每个父节点都会有两个子节点我们所学的堆即是顺序存储完全二叉树非完全二叉树- 链式存储链式结构顾名思义如同链子般即利用链表进行连接通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。所以我们在利用顺序结构创建堆时实际上是在控制数组的变化三.方案的选择普通数组 vs 堆如果要实时维护一组数据的最大值/最小值普通无序数组和有序数组有什么缺陷无序数组普通无序数组插入数据快但是每次获取或者删除数据需要全盘遍历 O(N)。有序数组取最大或最小值极快头和尾 但是插入或删除数据时需要移动大量元素来维护顺序 O(N)。堆大堆/小堆两头兼顾高效平衡找极值直接看堆顶 O(1)无论插入还是删除数据只需要向上向下调整 O(log N) 即可恢复堆性质。四.核心功能的逻辑实现1. 堆的结构体定义与物理架构为更好的控制堆我们将数组等定义在一个结构体中类似于顺序表的形式typedefintTypeData;// 将类型重命名typedefstructHeap{TypeData*a;// 定义数组intsize;// 有效个数intcapacity;// 空间容量}Hp;# 一.引言 在上一篇文章中我们讲到了**队列**队列讲究的是**绝对的公平**遵循 FIFOFirst In,First Out先进先出线性原则**堆**打破了存粹的时间顺序出队时不看是谁先来的而是看“**谁的优先级高/谁的数据最大或最小**”。**生动比喻**像是在车站排队买票先来后到而堆就像是医院的急诊室病情最严重的患者优先级最高哪怕最后进来也会被优先安排治疗。 # 二.核心概念逻辑树与物理数组的映射 堆本质是由完全二叉树构成如图在这里我们可以发现树的构成是由众多个节点所连接而成那么我们联系之前所学知识可以想到这种树的连接方式用链表最合适不过了毕竟从图中就可以发现他是相互连接起来的在这里我们就要讲二叉树的两种存储结构。 ##1二叉树的存储结构-顺序存储 顺序结构 顺序存储就是利用**数组**来进行数据存储只适合完全二叉树即每个父节点都会有两个子节点我们所学的堆即是顺序存储**完全二叉树****非完全二叉树****-链式存储链式结构**顾名思义如同链子般即利用链表进行连接通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。**所以我们在利用顺序结构创建堆时实际上实在控制数组的变化**# 三.方案的选择普通数组 vs 堆 如果要实时维护一组数据的最大值/最小值普通无序数组和有序数组有什么缺陷-**无序数组**普通无序数组插入数据快但是每次获取或者删除数据需要全盘遍历O(1)。-**有序数组**取最大或最小值极快头和尾 但是插入或删除数据时需要移动大量元素来维护顺序O(N)。-**堆大堆/小堆****两头兼顾高效平衡**找极值直接看堆顶O(1)无论插入还是删除数据只需要向上向下调整O(Log N)即可恢复堆性质。 # 四.核心功能的逻辑实现 ##1.堆的结构体定义与物理架构 为更好的控制堆我们将数组等定义在一个结构体中类似于顺序表的形式 ctypedefintTypeData;//将类型重命名typedefstructHeap{TypeData*a;//定义数组intsize;//有效个数intcapacity;//空间容量}Hp;2. 标准初始化与资源销毁//初始化voidHpInit(Hp*php){assert(php);php-aNULL;php-sizephp-capacity0;}//销毁voidHpDeatroy(Hp*php){free(php-a);php-aNULL;php-sizephp-capacity0;}这里释放掉数组后记得置空防止野指针出现3. 稳健入堆动态扩容与向上调整入堆的前提是堆内空间充足所以我们需要先判断是否空间充足再进行入堆操作voidIsFull(Hp*php){//插入前先判断空间是否充足if(php-sizephp-capacity){intnewcapacityphp-capacity0?4:php-capacity*2;TypeData*tmp(TypeData*)realloc(php-a,newcapacity*sizeof(TypeData));//判断是否扩容成功if(tmpNULL){return;}php-capacitynewcapacity;php-atmp;}}这里我们复习一个操作符“三目操作符” -------条件 1 2前的条件如果为真则执行1操作前的条件若为假则执行2有了以上扩容的知识我们就可以进行接下来的入堆操作了//入堆voidHpPush(Hp*php,intx){assert(php);//插入前先判断空间是否充足IsFull(php);//插入数据php-a[php-size]x;php-size;//插入后向上调整算法调整堆内元素顺序AdjustUp(php-a,php-size-1);}1向上调整法原理新元素“入堆”放在末尾逐层向上与父节点比较并交换从下往上“浮”。适用场景HpPush 插入元素、向上调整建堆。因为堆分为大堆和小堆那么堆便具有一定的大小关系所以为了插入数据后还能够维持相互的大小关系那么就要用到向上调整法我们先看例子不难看出这是一个大堆我们假若要再插入一个数字9 那么它的调整图是什么样子的呢因为我们是大堆在填加一个数据时是添加到了数组最后一个所以如果它的值很大则需要与上面的父节点进行交换//向上调整算法//交换voidSwap(TypeData*p1,TypeData*p2){TypeData tmp*p1;*p1*p2;*p2tmp;}voidAdjustUp(TypeData*a,intchild)//注意这里穿得是下标{//假设建大堆assert(a);while(child0){intparent(child-1)/2;if(a[parent]a[child]){Swap(a[parent],a[child]);childparent;}else{break;}}}遇到有子比父大的元素时则交换数据并且更新下标再次进行对比交换直到结束注意循环条件不能等于0 因为0节点无任何父节点。我们随便创造一个数组测试一下看功能是否正常。voidHeaptest01(){Hp hp;HpInit(hp);TypeData arr[]{1,5,6,4,3,8,7,9,12};for(inti0;isizeof(arr)/sizeof(TypeData);i){//入堆HpPush(hp,arr[i]);}HpDeatroy(hp);}由监视得到我们的HpPush功能正常。2思考为什么在向上调整法时传参不直接传入结构体指针呢而是传入数组呢4. 精准出堆堆顶删除与向下调整想象一下在一个堆中我们要删除堆顶数据如果直接删除再将数组内元素依次覆盖可以吗答案是不行如果直接覆盖那么顺序将会被打乱无法维持堆性质通俗点说亲属关系则会混乱。那么我们该如何解决这个问题呢//删除voidHpPop(Hp*php){assert(php);Swap(php-a[0],php-a[php-size-1]);php-size--;//向下调整算法AdjustDown(php-a,0,php-size);}向下调整法原理堆顶元素被替换后从根节点开始逐层向下与左右孩子中的较优者比较并交换从上往下“沉”。适用场景HpPop 删除堆顶、向下调整建堆。通过头尾交换在保证不破环堆性质的前提下将堆顶数据删除即 size–在对堆顶元素进行向下调整将父节点与较大的子节点进行比较互换然后更新下标将换下去的子节点继续与其子节点进行比较互换。//向下调整算法voidAdjustDown(TypeData*a,intparent,intn){assert(a);intchildparent*21;while(childn){//假设法建大堆if(child1na[child]a[child1]){child;}if(a[parent]a[child]){Swap(a[parent],a[child]);parentchild;childparent*21;}else{break;}}}细节避坑向下调整时右孩子越界的边界条件处理如 child 1 n。child满足界限child 1不一定满足界限。child满足child n - 1,所以child 1满足child 1 n;我们继上一次的代码继续测试一下删除功能是否正常。voidHeaptest01(){Hp hp;HpInit(hp);TypeData arr[]{1,5,6,4,3,8,7,9,12};for(inti0;isizeof(arr)/sizeof(TypeData);i){HpPush(hp,arr[i]);}//出堆HpPop(hp);HpDeatroy(hp);}正常。5.堆顶获取与判空堆顶获取即直接返回数组首元素即可1获堆顶TypeDataHpTop(Hp*php){assert(php);returnphp-a[0];}2判空错误示范boolHpEmpty(Hp*php){assert(php);if(php-aNULL){returntrue;}else{returnfalse;}}思考 为什么这样不可以数组为空确实是一种为空情况但是如果当数组内数据被HpPop函数删除完虽然数组内已经没有了元素但是它也不指向空所以这种判断方法并不严谨。所以只需要根据数组内元素个数是否为零来判断是否为空即可。boolHpEmpty(Hp*php){assert(php);returnphp-size0;}五.进阶应用与延伸1原地建堆1.向上调整法原地建堆 O(N * log N) )假设给定我们一个数组我们想将数组变成堆的形式那么按照以前的方法只需要通过HpPush函数依次入堆即可但是这样我们需要另外开辟一个空间来存储有没有办法不另外开辟空间来进行堆的构造呢voidHeaptest02(){//原地建堆TypeData arr[]{1,5,6,4,3,8,7,9,12};//若使用HpPush进行建堆则需要另外开辟空间而原地建堆则无需开辟额外空间for(inti1;isizeof(arr)/sizeof(TypeData);i){AdjustUp(arr,i);}}我们将第一个元素看成堆从第二个元素开始向上调整调整完向后移动一个数据单位再次进行向上调整从此达到原地调整即原地建堆2.向下调整法原地建堆 OlogN) )何为向下调整建堆呢也是在给定数组中进行数据的交换以此满足堆的性质。我们先给一个数组画出他的堆示意图向下调整原地建堆第一个操作对象是最后一个非叶子节点将整个堆分解成众多个堆依次进行从小往大的思想进行调整“先局部后整体”先从最小单位最后一个叶子节点开始调整假设我们要键大堆那么节点 3 与 节点1和4中较大的比较交换voidHeaptest03(){//向下调整原地建堆TypeData arr[]{2,9,5,3,7,6,4,1,4};intleaf(sizeof(arr)/sizeof(TypeData)-2)/2;for(intileaf;i0;i--){AdjustDown(arr,i,sizeof(arr)/sizeof(TypeData));}}2TopK问题假设给了我们一个文件文件中有众多数据让我们找出前K个最大的值我们该怎么办呢首先想到的就是将这些数组全部Push到堆中去然后依次首尾交换Pop出来但是这样假如数据量非常大我们堆所开辟的空间是非常之大的如果限定内存空间我们需要怎么做呢假如只给了我们1kb全量Push是肯定不可以的那么这时候我们就需要取前K个值建立一个小堆然后依次往后读取数据读取到的数据与堆顶元素进行对比如果比堆顶小则继续读取如果比堆顶大那么就取代堆顶元素并进行向下调整直到读取完整个文件内数据此时堆内元素则是所有元素中最大或者最小的元素。