【初阶数据结构】 归序而上的云阶 堆

点击展开/收起 文章目录文章目录1.堆的概念2.堆的接口实现堆的定义2.1 堆的初始化2.2 堆的销毁2.3 获取堆顶数据2.4 堆的向下调整2.5 堆的向上调整2.6 堆的插入2.7 堆顶数据删除2.8 堆的判空3.完整代码展示Heap.hHeap.c4.建堆方法1.向上调整建堆2.向下调整建堆希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力1.堆的概念堆是一种树形结构,本次我用数组来演示实现,属于完全二叉树,简单来说完全二叉树就是,除了最后一层每层都要是满的在讲解结构之前,我们讲解一个概念,父节点子节点,父节点是相对于子节点来说的,每一个节点都可以算是他下一层的父节点,直线相连的就是他的孩子就是子节点最后一层没有子节点堆的结构分类:1.大堆父节点一定要比所有子节点大子节点之间没有顺序要求2.小堆父节点一定要比所有子节点小子节点之间没有顺序要求2.堆的接口实现堆的定义与销毁初始化,与顺序表完全一致,这里不做过多的讲解,不会的可以去看看顺序表篇堆的定义typedefintHeapDataType;typedefstructHeapNode{HeapDataType*a;intsize;intcapacity;}Heap;2.1 堆的初始化voidHeapInit(Heap*ph){ph-aNULL;ph-capacityph-size0;}2.2 堆的销毁voidHeapDestory(Heap*ph){assert(ph);free(ph-a);ph-aNULL;ph-capacityph-size0;}2.3 获取堆顶数据堆顶数据就是第一个a[0]HeapDataTypeHeapTop(Heap*ph){assert(ph);assert(ph-size0);returnph-a[0];}在讲解向下调整之前我要讲讲父子节点关系由图可见;我们可以找到两种关系,child parent * 2 1parent (child - 1) / 2;(在这里会有child为偶数情况,(child-1)/2丢数据后的计算结果刚好是父节点)2.4 堆的向下调整主要目的:可以通过条件把小的数据往下调整,大的数据往上调,可以把最大的数据到最上面(这里只是是演示)可改变条件if (a[parent] a[child])达到相反的目的voidHeapDown(HeapDataType*a,intsize,intparent){//int parent 0;//注意这里不要写死了要传一个parentintchildparent*21;while(childsize)//孩子一定在数组范围了不可越界了{//判断左右孩子的大小,第一个条件是限制右孩子存在,只有右孩子存在才有可比性if(child1sizea[child]a[child1]){child;}if(a[parent]a[child]){Swap(a[parent],a[child]);parentchild;childparent*21;}else{//不满足时调到底了break;}}}2.5 堆的向上调整主要目的:可以通过条件把小的数据往上调整,大的数据往下调,可以把最小的数据到最上面(这里只是是演示)可改变条件if (a[parent] a[child])达到相反的目的voidHeapUp(HeapDataType*a,HeapDataType x,intsize){a[size]x;intchildsize;intparent0;while(child0){parent(child-1)/2;if(a[parent]a[child]){//这里就是普通的传指针交换数据Swap(a[parent],a[child]);}else{//不满足时调到底了break;}childparent;}}2.6 堆的插入我在这里建的是小堆voidHeapPush(Heap*ph,HeapDataType x){if(ph-sizeph-capacity){intnewcapacityph-capacity0?4:ph-capacity*2;HeapDataType*tmprealloc(ph-a,sizeof(HeapDataType)*newcapacity);if(tmpNULL){perror(realloc fail);exit(-1);}ph-atmp;ph-capacitynewcapacity;}//每次尾插数据,向上调整,把他跳到正确的位置,如果小了就往上走HeapUp(ph-a,x,ph-size);ph-size;}2.7 堆顶数据删除删除要保证删除后的数组还是一个堆,所以思路是把堆顶数据交换到堆尾,再向下调成新堆voidHeapPop(Heap*ph){assert(ph);assert(ph-size0);Swap(ph-a[0],ph-a[ph-size-1]);ph-size--;HeapDown(ph-a,ph-size);}2.8 堆的判空boolHeapEmpty(Heap*ph){returnph-size0;}3.完整代码展示Heap.h#includestdbool.h#includeassert.htypedefintHeapDataType;typedefstructHeapNode{HeapDataType*a;intsize;intcapacity;}Heap;//堆的初始化voidHeapInit(Heap*ph);//堆的销毁voidHeapDestory(Heap*ph);//获取堆顶数据HeapDataTypeHeapTop(Heap*ph);//堆的插入voidHeapPush(Heap*ph,HeapDataType x);//堆顶数据删除voidHeapPop(Heap*ph);//堆的判空boolHeapEmpty(Heap*ph);//堆的向下调整voidHeapDown(HeapDataType*a,intsize,intparent);//堆的向上调整voidHeapUp(HeapDataType*a,HeapDataType x,intsize);Heap.cvoidHeapInit(Heap*ph){ph-aNULL;ph-capacityph-size0;}voidHeapDestory(Heap*ph){assert(ph);free(ph-a);ph-aNULL;ph-capacityph-size0;}voidSwap(int*pa,int*pb){intc0;c*pb;*pb*pa;*pac;}voidHeapUp(HeapDataType*a,HeapDataType x,intsize){a[size]x;intchildsize;intparent0;while(child0){parent(child-1)/2;if(a[parent]a[child]){Swap(a[parent],a[child]);}else{break;}childparent;}}voidHeapPush(Heap*ph,HeapDataType x){if(ph-sizeph-capacity){intnewcapacityph-capacity0?4:ph-capacity*2;HeapDataType*tmprealloc(ph-a,sizeof(HeapDataType)*newcapacity);if(tmpNULL){perror(realloc fail);exit(-1);}ph-atmp;ph-capacitynewcapacity;}HeapUp(ph-a,x,ph-size);ph-size;}voidHeapDown(HeapDataType*a,intsize,intparent){//int parent 0;//注意这里不要写死了要传一个parentintchildparent*21;while(childsize){if(child1sizea[child]a[child1]){child;}if(a[parent]a[child]){Swap(a[parent],a[child]);parentchild;childparent*21;}else{break;}}}voidHeapPop(Heap*ph){assert(ph);assert(ph-size0);Swap(ph-a[0],ph-a[ph-size-1]);ph-size--;HeapDown(ph-a,ph-size);}HeapDataTypeHeapTop(Heap*ph){assert(ph);assert(ph-size0);returnph-a[0];}boolHeapEmpty(Heap*ph){returnph-size0;}我们为什么要有堆这个数据结构,因为在建成一个堆后,他的堆顶数据,大堆一定是最大的数,小堆一定是最小的数,**我们只需要每次把堆顶数据与最后一个数据交换再建新堆,就可以把数据排的有序,**在后面我会在八大排序专门讲解堆排序,还有个作用就是可以解决TopK问题,在下一次博客我会专门讲解Topk问题.下来我讲讲快速建堆的方法;4.建堆方法1.向上调整建堆voidHeapUp(HeapDataType*a,HeapDataType x,intsize){a[size]x;intchildsize;intparent0;while(child0){parent(child-1)/2;if(a[parent]a[child]){//这里就是普通的传指针交换数据Swap(a[parent],a[child]);}else{//不满足时调到底了break;}childparent;}}for(inti1;i11;i){HeapUp(a,i,size);}2.向下调整建堆voidHeapDown(HeapDataType*a,intsize,intparent){//int parent 0;//注意这里不要写死了要传一个parentintchildparent*21;while(childsize)//孩子一定在数组范围了不可越界了{//判断左右孩子的大小,第一个条件是限制右孩子存在,只有右孩子存在才有可比性if(child1sizea[child]a[child1]){child;}if(a[parent]a[child]){Swap(a[parent],a[child]);parentchild;childparent*21;}else{//不满足时调到底了break;}}}for(intisize-1;i0;i--){//从倒数第二层开始向下调整HeapDown(a,i,(i-2)/2);}这里有两种建堆方法谁更有优势呢,我们该选择哪一种呢?这里我们就要计算一下建堆的复杂度向上调整的复杂度计算向下调整的复杂都计算希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力