【数据结构】堆（Heap）详解----定义堆、初始化，删除、插入、销毁、判空、取堆顶

文章目录

提示：以下是本篇文章正文内容

一、堆的概念及其性质：

堆的概念：

堆：是一种特殊的完全二叉树，使用数组进行存储，其所有的父结点大于等于或者小于等于它们的子结点，所以堆分为大根堆和小根堆。
大根堆（最大堆）：：所有的父结点大于等于它们的子结点，堆顶是最大值。
小根堆（最小堆）：：所有的父结点小于等于它们的子结点，堆顶是最小值。
举例：

堆的性质：

对于具有n个结点的完全二叉树，若按照从上至下，丛左至右的数组顺序对所有结点从0开始编号，则对于序号为i的节点：
1.若i=0，i为根节点编号，无双亲结点。
2.若i>0，i位置结点的双亲序号：（i-1)/2；
3.若2i+1<n，左孩子序号：2i+1。
4.若21+2<n，右孩子序号：2i+2。

二、堆的定义及其基础操作的代码实现（C语言版）

因为堆的定义以及销毁、初始化很简单，就不赘述啦，直接看代码。难点主要在于堆的插入和删除，我们会用到两种方法向上调整法和向下调整法，我会详细讲述。

1.定义堆

typedefint HPDataType;typedefstructHeap{
    HPDataType* _arr;int _size;//有效数据个数int _capacity;//空间大小}Heap;

2.堆的初始化

voidHeapInit(Heap* hp){assert(hp);
    hp->_arr =NULL;
    hp->_capacity = hp->_size =0;}

3.堆的销毁

voidHeapDestory(Heap* hp){assert(hp);if(hp->_arr)free(hp->_arr);
    hp->_arr =NULL;
    hp->_capacity = hp->_size =0;}

4.堆的插入

对于堆的插入我们可以分两种情况：
1.插入的结点是根结点，那么就直接hp->_arr[hp->_size] = x就行。
2.若插入的不是根节点，那么我们不仅要hp->_arr[hp->_size] = x，还需要进行向上调整。
向上调整法（以小根堆为例，掌握啦小根堆大根堆也就会啦~）：
其思想主要是将元素直接插入到最后一个位置，若不是根结点，则需要与其父结点进行比较，若比父结点小，则与父节点进行交换，一直重复该操作，直到孩子结点大于等于父结点或者到根结点。
为了方便柚柚们理解，我来为柚柚们讲一个例子：

以6 5 4 3为例：
第一次插入6的时候，为根节点，此时直接插入作为根结点，不需要调整，_size++。

第二次插入5的时候，此时5有父结点，其父节点序号为(1-1)/2 = 0，即为6，发现孩子结点比父结点小，我们就要把它们交换，交换之后让孩子结点指向序号为0的结点，此时为根节点不需要调整，插入完成，_size++。

第三次插入4，此时4有父结点，其父节点序号为(2-1)/2 = 0，即为5，发现孩子结点比父结点小，所以我们要把它们交换，交换之后让孩子结点指向序号为0的结点，此时为根节点不需要调整，插入完成，_size++。

第四次插入3，此时3有父结点，其父节点为(3-1)/2 = 1，即为6，发现孩子结点比父结点小，所以我们要把它们交换，交换之后让孩子结点指向序号为1的结点，然后再让1这个位置的结点与其父结点比较，其父结点为(1-1)/2 = 0,即为4，发现孩子结点比父结点大，我们就不需要再进行调整，插入完成，_size++。

整个过程就是这样，其实是很好理解，看完图应该就能够理解啦~

代码实现：

voidSwap(int* x,int* y){int tmp =*x;*x =*y;*y = tmp;}//向上调整法voidAdjustUp(HPDataType* arr,int child){int parent =(child -1)/2;while(child >0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换{if(arr[child]< arr[parent])//若孩子结点比父结点小则交换{Swap(&arr[parent],&arr[child]);
            child = parent;
            parent =(child -1)/2;}else{break;}}}//堆的插入voidHeapPush(Heap* hp, HPDataType x){assert(hp);if(hp->_capacity == hp->_size){int newCapacity = hp->_capacity ==0?4:2* hp->_capacity;//分配空间，因为刚开始容量为0，所以要特殊处理
        HPDataType* tmp =(HPDataType*)realloc(hp->_arr,newCapacity *sizeof(HPDataType));if(tmp ==NULL)exit(1);//分配内存失败，结束程序
        hp->_arr = tmp;
        hp->_capacity = newCapacity;}
    hp->_arr[hp->_size]= x;AdjustUp(hp->_arr, hp->_size);//向上调整法
    
    hp->_size++;}

5.堆的删除

对于堆的删除我们需要注意的是我们删除的是根结点，为了方便删除根节点，我们将根结点与最后一个结点进行交换，然后_size–，就把根节点删啦，但是此时打乱了堆的顺序，根结点可能就不是最小的啦，所以我们要对根节点进行向下调整。具体步骤就是，让交换之后的根结点与它的孩子结点比较，若比孩子结点大，则与孩子结点交换，然后让父节点指向该孩子结点，直到孩子结点的下标大于等于n(结点的个数）或者比其孩子结点都小；若比孩子结点们小，则结束，删除完成，其实理解了向上调整，向下调整就很容易理解啦，所以我就不再举例子啦。

//向下调整法voidAdjustDown(HPDataType* arr,int parent,int n){int child = parent *2+1;//左孩子while(child < n){//找左右孩子中找最小的if(child +1< n && arr[child]> arr[child +1]){
            child++;}if(arr[child]< arr[parent]){Swap(&arr[child],&arr[parent]);
            parent = child;
            child = parent *2+1;}else{break;}}}voidHeapPop(Heap* php){assert(php && php->_size);Swap(&php->_arr[0],&php->_arr[php->_size -1]);--php->_size;AdjustDown(php->_arr,0, php->_size);}

6.取堆顶的数据

HPDataType HeapTop(Heap* php){assert(php && php->_size);return php->_arr[0];}

7.堆的数据个数

intHeapSize(Heap* hp){return hp->_size;}

8.堆的判空

bool HeapEmpty(Heap* php){assert(php);return php->_size ==0;}

总结：

若是还没有理解向上调整法和向下调整法，柚柚们可以多看看代码多画画图，还有就是自己搞几个样例跟着程序调试，就可以搞懂啦~，日后还会更新堆排还有其它数据结构的知识，感兴趣的柚柚们可以三连，关注博主喔！