【数据结构 C语言版】第七篇 堆

【数据结构 C语言版】第七篇 堆

写在前面

更新情况记录：
最近更新时间更新次数2022/10/231
参考博客与书籍以及链接：
（非常感谢这些博主们的文章，将我的一些疑问得到解决。）
参考博客链接或书籍名称《数据结构与算法分析 C语言描述》代码随想录总目录：目前数据结构文章太少，没有写。

正文

文章目录

1.堆（heap）

堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。

这样的树称为完全二叉树（complete binary tree）。

2.堆的概念

大堆：根节点最大

小堆：根节点最小

3.堆的性质

• 堆中某个节点的值总是不大于或不小于其父节点的值
• 堆总是一课完全二叉树
• 公式（注：数组是从0开始的，如果是从1开始的就不是这样）：

leftChild=Parent*2+1；

rightChild=Parent*2+2;

Parent=(Child-1)/2;

4.堆实现（以建小堆为例）

注意：有的教材第0位不存数字,也就是从1开始。但是本文的堆数组是从0开始的。

1.堆的结构与声明

堆的结构，堆是用数组实现的。

typedefint HPDataType;typedefstructHeap{
    HPDataType* a;int size;int capacity;}Heap;

堆的接口：

// 堆的初始化voidHeapInit(Heap* hp);// 堆的销毁voidHeapDestory(Heap* hp);// 堆的插入voidHeapPush(Heap* hp, HPDataType x);// 堆的删除voidHeapPop(Heap* hp);// 取堆顶的数据
HPDataType HeapTop(Heap* hp);// 堆的数据个数intHeapSize(Heap* hp);// 堆的判空intHeapEmpty(Heap* hp);//向上调整voidAdjustUp(HPDataType* a,int child);//向下调整voidAdjustDown(HPDataType* a,int n,int parent);//交换voidswap(HPDataType* child, HPDataType* parent);//堆的打印voidHeapPrint(Heap* hp);

2.堆初始化

voidHeapInit(Heap* hp){assert(hp);
    hp->a =NULL;
    hp->size = hp->capacity =0;}

3.堆的销毁

// 堆的销毁voidHeapDestory(Heap* hp){assert(hp);free(hp->a);
    hp->a =NULL;
    hp->capacity = hp->size =0;}

4.堆的插入

【思路】：

堆尾插入x，然后向上调整。

【代码】：

voidHeapPush(Heap* hp, HPDataType x){assert(hp);//如果空间不够就扩容if(hp->capacity == hp->size){int newCapaciy = hp->capacity ==0?4: hp->capacity *2;
        HPDataType* tmp =(HPDataType*)realloc(hp->a,sizeof(HPDataType)* newCapaciy);if(tmp ==NULL){perror("malloc fail");exit(-1);}
        hp->a = tmp;
        hp->capacity = newCapaciy;}//这边才是插入代码
    hp->a[hp->size++]= x;AdjustUp(hp->a, hp->size -1);}

5.堆顶的删除

【思路】：

将堆顶与最后一个元素交换。随后换到堆顶的元素向下调整，size要-1。

【代码】：

voidHeapPop(Heap* hp){assert(hp);assert(!HeapEmpty(hp));swap(&hp->a[0],&hp->a[hp->size -1]);
    hp->size--;AdjustDown( hp->a,hp->size,0);}

6.向上调整

【思路】：

因为本文建的是小堆，所以如果孩子小于双亲，那么就交换（小堆：parent>child）。

如果parent>child一直存在，那么就一直执行下去，直至child > 0;

起始位置：child的位置。

最后：走到a[child]>a[parent]的时候,或者child<=0

【代码】：

voidAdjustUp(HPDataType* a,int child){int parent =(child -1)/2;while(child >0){if(a[child]< a[parent]){swap(&a[child],&a[parent]);
            child = parent;
            parent =(child -1)/2;}else{break;}}}

7.向下调整

【思路】：

如果Child<parent就互换。

起始位置：parent

终止位置：走到a[child]>a[parent]的时候,或者Child>=n

【代码】：

//向下调整voidAdjustDown(HPDataType* a,int n,int parent){//可以默认最小的孩子(左右孩子中)是左孩子//如果右孩子更小，就更新minChild。int minChild = parent *2+1;while(minChild < n){if(minChild +1< n && a[minChild +1]< a[minChild]){
            minChild++;}if(a[minChild]< a[parent]){swap(&a[minChild],&a[parent]);
            parent = minChild;
            minChild = parent *2+1;}else{break;}}}

5. 源代码

heap.h

#include<stdio.h>#include<assert.h>#include<stdlib.h>//这里的代码是建小堆。typedefint HPDataType;typedefstructHeap{
    HPDataType* a;int size;int capacity;}Heap;voidHeapInit(Heap* hp);// 堆的销毁voidHeapDestory(Heap* hp);// 堆的插入voidHeapPush(Heap* hp, HPDataType x);// 堆的删除voidHeapPop(Heap* hp);// 取堆顶的数据
HPDataType HeapTop(Heap* hp);// 堆的数据个数intHeapSize(Heap* hp);// 堆的判空intHeapEmpty(Heap* hp);//向上调整voidAdjustUp(HPDataType* a,int child);//向下调整voidAdjustDown(HPDataType* a,int n,int parent);//交换voidswap(HPDataType* child, HPDataType* parent);voidHeapInit(Heap* hp);voidHeapPrint(Heap* hp);

heap.c

#include"Heap.h"voidHeapInit(Heap* hp){assert(hp);
    hp->a =NULL;
    hp->size = hp->capacity =0;}// 堆的销毁voidHeapDestory(Heap* hp){assert(hp);free(hp->a);
    hp->a =NULL;
    hp->capacity = hp->size =0;}// 堆的插入voidHeapPush(Heap* hp, HPDataType x){assert(hp);if(hp->capacity == hp->size){int newCapaciy = hp->capacity ==0?4: hp->capacity *2;
        HPDataType* tmp =(HPDataType*)realloc(hp->a,sizeof(HPDataType)* newCapaciy);if(tmp ==NULL){perror("malloc fail");exit(-1);}
        hp->a = tmp;
        hp->capacity = newCapaciy;}
    hp->a[hp->size++]= x;AdjustUp(hp->a, hp->size -1);}// 堆的删除voidHeapPop(Heap* hp){assert(hp);assert(!HeapEmpty(hp));swap(&hp->a[0],&hp->a[hp->size -1]);
    hp->size--;AdjustDown( hp->a,hp->size,0);}// 取堆顶的数据
HPDataType HeapTop(Heap* hp){assert(hp);assert(!HeapEmpty(hp));return hp->a[0];}// 堆的数据个数intHeapSize(Heap* hp){assert(hp);return hp->size;}// 堆的判空intHeapEmpty(Heap* hp){assert(hp);return hp->size ==0;}//向上调整voidAdjustUp(HPDataType* a,int child){int parent =(child -1)/2;while(child >0){if(a[child]< a[parent]){swap(&a[child],&a[parent]);
            child = parent;
            parent =(child -1)/2;}else{break;}}}//向下调整voidAdjustDown(HPDataType* a,int n,int parent){int minChild = parent *2+1;while(minChild < n){if(minChild +1< n && a[minChild +1]< a[minChild]){
            minChild++;}if(a[minChild]< a[parent]){swap(&a[minChild],&a[parent]);
            parent = minChild;
            minChild = parent *2+1;}else{break;}}}voidswap(HPDataType* child, HPDataType* parent){
    HPDataType tmp =*child;*child =*parent;*parent = tmp;}voidHeapPrint(Heap* hp){assert(hp);assert(!HeapEmpty(hp));int i =0;for(i =0; i < hp->size; i++){printf("%d ", hp->a[i]);}printf("\n");}

本文完。