个人主页：欢迎大家光临——>沙漠下的胡杨

  各位大帅哥，大漂亮

 如果觉得文章对自己有帮助

 可以一键三连支持博主

 你的每一分关心都是我坚持的动力

 

 ☄： 本期重点：二叉树实现堆

  希望大家每天都心情愉悦的学习工作。 

目录

堆的定义：

堆的存储结构：

堆的代码实现：

头文件篇：

源文件篇：

堆的初始化：

堆的打印：

堆的销毁：

返回堆顶元素：

判断堆元素是否为空：

返回堆的元素个数：

堆的插入和向上调整：

堆的删除和向下调整：

实现代码正确性：

整体代码：

头文件：

源文件：

堆的定义：

 我们认为堆是一个完全二叉树，并且堆中的父子关系 有且只有一种，要么是父亲结点大于等于孩子结点，要么是父亲节点小于等于孩子结点。

我们根据根节点在堆中的大小，来确定是大堆还是小堆，如果根节点在堆中最大，则是大根堆；如果根节点在堆中最小，则是小根堆。

堆的存储结构：

我们知道一般的二叉树使用链式存储，但是完全二叉树可以使用数组进行存储。

一般的二叉树使用数组存储，会造成大量的空间浪费，而完全二叉树，就不会哦！

 又因为堆刚好是完全二叉树，所以我们使用数组存储。

上述示意图中，二叉树的部分是我们想象中的逻辑结构，下面数组部分是我们实际在数组中的存储结构。 

堆的代码实现：

头文件篇：

首先我们和顺序表一样写出，头文件，存储结构，函数接口。

#pragma once#define  _CRT_SECURE_NO_WARNINGS#include #include #include #include typedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capaticy;}HP;void Swap(HPDataType* p1, HPDataType* p2);//交换void AdjustDwon(HPDataType* a, int size, int parent);//向下调整 (时间复杂度O(N))void AdjustUp(HPDataType* a, int child);//向上调整(时间复杂度O(N))void HeapPrint(HP* php);//打印void HeapInit(HP* php);//初始化void HeapDestroy(HP* php);//销毁void HeapPush(HP* php, HPDataType x);//插入void HeapPop(HP* php);//删除HPDataType HeapTop(HP* php);//返回堆顶元素bool HeapEmpty(HP* php);//判空int HeapSize(HP* php);//返回堆的元素个数。

源文件篇：

上述的一些接口比较简单，我们就直接放代码，比较难的接口，我们详细说。

堆的初始化：

void HeapInit(HP* php)//初始化{assert(php);php->a = NULL;php->size = php->capaticy = 0;}

堆的打印：

void HeapPrint(HP* php)//打印{assert(php);for (int i = 0; i size; i++){printf("%d ", php->a[i]);}printf("\n");}

堆的销毁：

void HeapDestroy(HP* php)//销毁{assert(php);free(php->a);php->a = NULL;php->size = php->capaticy = 0;}

返回堆顶元素：

HPDataType HeapTop(HP* php)//返回堆顶元素{assert(php);assert(!HeapEmpty(php));return php->a[0];}

判断堆元素是否为空：

bool HeapEmpty(HP* php)//判空{assert(php);return php->size == php->capaticy;}

返回堆的元素个数：

int HeapSize(HP* php)//返回堆的元素个数。{assert(php);return php->size;}

下面我们要讲的是堆的最重要部分 插入 和 删除 功能，以及向上调整和向下调整算法。

堆的插入和向上调整：

我们建堆插入时，一般会插入在动态数组的最后一个元素处插入数据，然后在进行调整，这个调整叫向上调整算法。

 我们在调整时，满足父亲节点的下标和孩子节点的下标满足一个公式，P = （C-1）/ 2，

利用这一公式我们可以进一步找到父亲节点，然后调整，代码如下：

void AdjustUp(HPDataType* a, int child)//向上调整{int parent = (child - 1) / 2;//找到父亲节点while (child > 0)//如果child等于0，表示调整到根，不可在调整返回。{//孩子大于父亲就交换（大根堆）if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void HeapPush(HP* php, HPDataType x)//插入{assert(php);if (php->size == php->capaticy){int NewCapaticy = php->capaticy == 0 ? 4 : 2 * php->capaticy;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*NewCapaticy);if (tmp == NULL){printf("realloc fail\n");exit(-1);}php->a = tmp;php->capaticy = NewCapaticy;}php->a[php->size] = x;php->size++;//最后要给的是孩子的下标，是size-1.AdjustUp(php->a, php->size - 1);}

堆的删除和向下调整：

同样在堆删除数据时，会先交换最后一个数据和根，然后让根进行向下调整。

我们也使用了公式： C（左孩子）= P*2 +1。

我们依据上图实现下代码吧：

void AdjustDwon(HPDataType* a, int size, int parent)//向下调整{int child = parent * 2 + 1;//左孩子while (child < size)//孩子节点下，到size结束{   //要在确定有右孩子的情况下，右孩子大于左孩子，就使用右孩子（大堆）if (child + 1 < size && a[child]  a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void HeapPop(HP* php)//删除{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDwon(php->a, php->size, 0);}

头文件：

#pragma once#define  _CRT_SECURE_NO_WARNINGS#include #include #include #include typedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capaticy;}HP;void Swap(HPDataType* p1, HPDataType* p2);//交换void AdjustDwon(HPDataType* a, int size, int parent);//向下调整 (时间复杂度O(N))void AdjustUp(HPDataType* a, int child);//向上调整(时间复杂度O(N))void HeapPrint(HP* php);//打印void HeapInit(HP* php);//初始化void HeapDestroy(HP* php);//销毁void HeapPush(HP* php, HPDataType x);//插入void HeapPop(HP* php);//删除HPDataType HeapTop(HP* php);//返回堆顶元素bool HeapEmpty(HP* php);//判空int HeapSize(HP* php);//返回堆的元素个数。

源文件：

#include "Heap.h"void Swap(HPDataType* p1, HPDataType* p2)//交换{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}void HeapPrint(HP* php)//打印{assert(php);for (int i = 0; i size; i++){printf("%d ", php->a[i]);}printf("\n");}void HeapInit(HP* php)//初始化{assert(php);php->a = NULL;php->size = php->capaticy = 0;}void HeapDestroy(HP* php)//销毁{assert(php);free(php->a);php->a = NULL;php->size = php->capaticy = 0;}HPDataType HeapTop(HP* php)//返回堆顶元素{assert(php);assert(!HeapEmpty(php));return php->a[0];}bool HeapEmpty(HP* php)//判空{assert(php);return php->size == php->capaticy;}int HeapSize(HP* php)//返回堆的元素个数。{assert(php);return php->size;}void AdjustDwon(HPDataType* a, int size, int parent)//向下调整{int child = parent * 2 + 1;//左孩子while (child < size)//孩子节点下，到size结束{   //要在确定有右孩子的情况下，右孩子大于左孩子，就使用右孩子（大堆）//想变为小根堆，大于变小于（child +1 <size不变）if (child + 1 < size && a[child]  a[parent])//想变为小根堆，大于变小于{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void AdjustUp(HPDataType* a, int child)//向上调整{int parent = (child - 1) / 2;//找到父亲节点while (child > 0)//如果child等于0，表示调整到根，不可在调整返回。{//孩子大于父亲就交换（大根堆）if (a[child] > a[parent])//想变为小根堆，大于变小于{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void HeapPush(HP* php, HPDataType x)//插入{assert(php);if (php->size == php->capaticy){int NewCapaticy = php->capaticy == 0 ? 4 : 2 * php->capaticy;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*NewCapaticy);if (tmp == NULL){printf("realloc fail\n");exit(-1);}php->a = tmp;php->capaticy = NewCapaticy;}php->a[php->size] = x;php->size++;//最后要给的是孩子的下标，是size-1.AdjustUp(php->a, php->size - 1);}void HeapPop(HP* php)//删除{assert(php);assert(!HeapEmpty(php));Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDwon(php->a, php->size, 0);}