关系：

上面这一个图就是完全二叉树

比如上面的树形结构就是非完全二叉树

很多性质在前面已经提到过了，这里我们来证明性质5~

1.假设⼀个二叉树有 a 个度为2的节点， b 个度为1的节点， c 个叶节点，则这个二叉树的边数（连接两个结点的线的条数）是2a+b

2.由于共有 a+b+c 个节点，所以边数等于 a+b+c-1

结合上⾯两个公式： 2a+b = a+b+c-1 ，即： a = c - 1,所以n0= n2 + 1

例：

二叉树存储结构

如果有⼀个关键码的集合 K = {K 0 , K 1 , K 2 , ... ， K n -1 } ，把它的所有元素按完全二叉树的顺序存储方式 存储，在⼀个⼀维数组中，如果满足： K i <= K 2∗ i+1 称为小堆，如果满足 K i >= K 2∗ i +1 且 K i <= K 2∗ i +2 称为大 堆。（i=0,1,2……n-1）

将 根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆 。不难得出

大根堆的堆顶是堆中最大的结点，小根堆堆顶是堆中最小的结点。

特点

我们可以看出堆的特点：

1)堆中某个结点的值总是不大于其父结点的值（大根堆—— 父结点大 ）或者不小于其父结点的值（小根堆—— 父结点小 ）

2)堆总是⼀棵完全二叉树

对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：

1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ，说明 i 为根结点编号，无双亲结点

2. 若 2i+1<n ，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子

3. 若 2i+2<n ，右孩子序号： 2i+2 ， 2i+2>=n 否则无右孩子

堆的实现

定义堆的结构

我们知道堆的底层逻辑是数组，与我们前面学习的顺序表就类似了，我们一起来定义堆的结构~

//重定义存储数据类型
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;//底层逻辑是数组int size;//保存的数据个数int capacity;//数据容量大小
}HP;

初始化

首先将数组置为空，size和capacity值为0

注意：传地址形参的改变才会影响实参，使用指针来接收

//初始化
void HPInit(HP* php)
{assert(php);//传过来的地址有效php->arr = NULL;php->size = php->capacity = 0;
}

//test.c
#include"Heap.h"void test1()
{HP hp;HPInit(&hp);//传地址}int main()
{test1();return 0;
}

我们可以看见成功的进行了初始化~

销毁堆

有初始化，当然也有销毁，堆的实现数组是动态申请的内存空间，所以需要对动态申请的内存空间进行释放并且及时置为空，避免成为野指针，size和capacity也重新变为0.

代码：

//销毁
void HPDestory(HP* php)
{assert(php);free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}

往堆里面插入数据

前面判断空间是否足够操作与顺序表相同，这里就不多说，我们来看看堆不一样的地方，我们知道堆可以分为大堆和小堆，那么我们插入的数据默认插入在最后一个编号的位置，如果我们想让这一个堆成为一个大堆或者小堆是不是就需要进行调整，怎么调整呢？

如果现在我们需要建一个大堆，我们将这一个结点与它的父结点进行比较，如果比父结点大就进行交换，然后让子结点走到父结点的位置，原来的父结点走到它自己的的父结点，如果比父结点小就退出循环，循环结束条件是子结点走到0或者子结点小于父结点。

常见问题：

1.有人可能会问怎么找到当前结点的父结点呢？

如果当前结点编号是 i ，结合前面的二叉树的性质，那么【 （ i -1）/2 】不就是父结点的编号了吗？

2.可能还有人会问如果子结点是右结点，我们难道不需要将它与左结点比较再继续往上面调整吗？

答案是不需要，因为每一次插入数据都与父结点进行了比较，那么与左结点相比父结点就是较大或者较小的结点，只需要将当前结点与父结点比较就可以了，就不需要进行与左孩子结点比较了。

代码实现：

//交换
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp = *a;*a = *b;*b = tmp;
}//向上调整数据
AdjustUP(HPDataType* arr, int child)
{//这里不需要传HP*类型的，我们可以直接通过数组下标调整就可以了，更加方便//当前结点父结点int parent = (child - 1) / 2;while (child > 0){// > 大堆// < 小堆if (arr[child] > arr[parent]){//当前结点较大进行交换Swap(&arr[child], &arr[parent]);//往上面走//孩子结点走到父结点的位置child = parent;//走到新的父结点parent = (child - 1) / 2;}else{//提前跳出循环break;}}
}//往堆里面插入数据
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->size == php->capacity)//空间满了扩大容量{int newcapacity = (php->capacity == 0) ? 4 : 2 * (php->capacity);HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);//创建临时变量避免开辟空间失败if (tmp == NULL){perror("realloc fail");exit(1);}//开辟空间成功php->arr = tmp;php->capacity = newcapacity;}//往后面插入数据php->arr[php->size] = x;//放入数据//向上调整数据AdjustUP(php->arr, php->size);//数据个数++php->size++;
}

判空

这里的代码相信有了前面的基础就不用多说了~

// 判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;//数据个数为0说明为空
}

堆的数据个数

这里直接返回size就好了~

//求size
int HPSize(HP* php)
{assert(php);return php->size;
}

删除堆顶的数据

这又是一个重头戏了，我们一点点来看~

删除堆顶的数据，如果我们像顺序表那样进行头删，那么后面的每一个数据移到前面的一个编号，那么我们是不是也就改变了原来的树形结构呢？所以我们这里换一种思路

同样是以大堆为例，首先将堆顶的数据与最后一个编号的数据进行交换，将数据个数--也就将最后一个编号的数据删除，然后从堆顶往下面进行调整，我们堆顶也就是一个父结点，我们找到它的左孩子结点，左孩子结点+1就是右孩子结点，左右孩子结点进行比较，找到最大的孩子结点与父结点比较，如果比父结点大就进行交换，接着往下面走，父结点走到子结点的位置，子结点到新的左孩子结点，循环结束条件是当孩子结点编号大于数据个数或者子结点比父结点小。

常见问题：

1.怎么找到孩子结点？

结合二叉树的性质，如果父结点编号为parent，那么左孩子结点编号为2*parent+1，右孩子结点编号为2*parent+2.

2.为什么只需要找到调整较大/较小的孩子结点

这就不得不说我们这个方法的妙处了，因为我们首先将堆顶的数据与最后一个编号的数据进行交换，这样原来的堆的其他结构是没有改变的。

代码实现：

//向下调整数据
AdjustDown(HPDataType* arr, int parent, int size)
{assert(arr);//当前父结点的左孩子结点int child = 2 * parent + 1;while (child < size)//左孩子结点编号必须小于结点个数{//如果右孩子结点存在!!!// 并且右孩子结点>左孩子结点，那么child就是右孩子结点编号if (child + 1 < size && (arr[child + 1] > arr[child])){child++;}//如果父结点小于孩子结点就进行交换if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);//继续往下面调整parent = child;child = 2 * parent + 1;}//如果父结点大于孩子结点就提前结束循环else{break;}}
}// 删除堆顶的数据
void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));//堆不为空才可以删除数据//先交换第一个数据和最后一个数据//结点个数-1就是最后一个结点的编号Swap(&php->arr[0], &php->arr[php->size - 1]);//删除最后一个数据，数据个数--php->size--;//向上调整数据//传递地址和父结点下标和结点总个数//使用下标对数组进行调整AdjustDown(php->arr, 0, php->size);
}// 判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;//数据个数为0说明为空
}

获取堆顶数据

堆顶就是编号为0的结点，直接返回数据就好了

//获取堆顶数据
HPDataType HPTop(HP* php)
{assert(php);//堆不能为空assert(!HPEmpty(php));return php->arr[0];
}

堆排序

接下来我们来看看堆排序~首先我们试一试打印我们之前创建的堆~

这里我们创建了一个大堆，打印数据得到的是一个降序，那我们创建一个小堆呢？通过前面我们知道只需要将调整代码进行改变就可以了~

//向上调整数据
AdjustUP(HPDataType* arr, int child)
{//当前结点父结点int parent = (child - 1) / 2;while (child > 0){// > 大堆// < 小堆if (arr[child] < arr[parent]){//当前结点较大进行交换Swap(&arr[child], &arr[parent]);//往上面走//孩子结点走到父结点的位置child = parent;//走到新的父结点parent = (child - 1) / 2;}else{//提前跳出循环break;}}
}

我们神奇的发现这不是升序吗？那如果使用堆进行排序是不是只需要创建一个大堆排降序，创建一个小堆排升序就可以了呢？别急，我们再来看看，如果我们再插入一个数据呢？

这里我们可以发现小堆实现升序没有问题，但是我们想通过大堆实现降序就出现问题了，有人又给出新的方法，如果是需要对一个数组进行排序，我们首先将数组的元素插入到堆中，如果创建的是大堆我们就可以每一次取堆顶元素重新放入数组中，再删除堆顶，这样每一次堆顶元素都是最大的放到数组中，这不就实现了降序嘛？我们一起来看看~

void test2()
{int arr[] = { 3,5,6,1,9,2,7,8,4,0 };int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;HP hp;HPInit(&hp);//初始化for (i = 0; i < sz; i++){//将下标为i的数据插入HPPush(&hp, arr[i]);}i = 0;//i及时置为0while (!HPEmpty(&hp)){//每次取堆顶数据放入arrarr[i++] = HPTop(&hp);HPPop(&hp);}for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}

这里达到了我们想要的效果，事实上，真正的堆排序并不是这种写法，堆排序是借助堆的算法思
想，而不能够直接使用堆的数据结构来辅助实现～

那么怎么样才进行真正的堆排序呢？我们一起来看看~

真正的堆排序

堆排序是借助堆的算法思想，而不能够直接使用堆的数据结构来辅助实现～

结合概念，我们不能直接使用堆这样一种数据结构，同时我们知道堆的底层逻辑是数组，所以

我们堆排序首先给给定的数组进行建堆，使用向下或者向上调整的算法进行堆的创建，然后再进行对堆进行排序~

void HeapSort(int* arr, int sz)
{//根据给定的arr建堆//调整数组arr的数据//1.向下的算法建堆//child = sz - 1(最大的孩子结点下标）//parent = （ sz - 1 - 1)/2  (最大的父结点下标）int i = 0;for (i = (sz - 1 - 1) / 2; i >= 0;i--){AdjustDown(arr, i, sz);//AdjustDown参数//AdjustDown(HPDataType* arr, int parent, int size)}//2.向上的算法建堆//for(i = 0;i < sz; i++)//{//	AdjustUP(arr, i);//	//AdjustUP参数//AdjustUP(HPDataType* arr, int child)//}//进行堆排序//升序——大堆// 堆顶元素就是当前最大的，交换之后最后面的元素最大//降序——小堆//堆顶元素就是当前最小的，交换之后最后面的元素最小int end = sz - 1;while (end > 0){//一个个调整Swap(&arr[0], &arr[end]);//堆顶元素就是当前最大的，交换之后最后面的元素最大AdjustDown(arr, 0, end);//这里end就代表调整个数// 数组下标为end的元素已经是最大的不需要调整//最后面元素变化end--;}
}
void test3()
{int arr[] = { 3,5,6,1,9,2,7,8,4,0 };int sz = sizeof(arr) / sizeof(arr[0]);HeapSort(arr, sz);int i = 0;for (i = 0; i < sz; i++){printf("%d ", arr[i]);}
}

测试1：

测试2：

常见问题：

1.为什么建堆之后向下调整，最后一个传参是end呢？

首先我们来看看向下调整的代码，我们可以看到这里的size代表的是调整的数据个数，并不代表着调整的最后一个元素的下标，所以在这个大堆的例子中，首先使用向上或者向下的算法将数组建成堆的形式，然后将第一个元素与最后一个元素交换位置（大堆第一个元素最大，交换之后最后一个元素最大，再次调整，数据个数每次减少一个），这也就是为什么建大堆排升序，建小堆排降序

//向下调整数据
AdjustDown(HPDataType* arr, int parent, int size)
{assert(arr);//当前父结点的左孩子结点int child = 2 * parent + 1;while (child < size)//左孩子结点编号必须小于结点个数{//如果右孩子结点存在!!!// 并且右孩子结点>左孩子结点，那么child就是右孩子结点编号if (child + 1 < size && (arr[child + 1] > arr[child])){child++;}//如果父结点小于孩子结点就进行交换if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);//继续往下面调整parent = child;child = 2 * parent + 1;}//如果父结点大于孩子结点就提前结束循环else{break;}}
}

2）堆排序的时间复杂度——O(n * log n)

外层while循环O(n），内层向下调整算法，调整log2 n次，所以时间复杂度为O(n * log n)

不同建堆方式时间复杂度比较

这里我们不是需要使用向上或者向下的算法对给定的数组进行建堆吗？接下来我们结合复杂度知识来更加准确的看看不同建堆方式时间复杂度~

向上算法进行建堆

代码：

//2.向上的算法建堆for(i = 0;i < sz; i++)
{AdjustUP(arr, i);//AdjustUP参数//AdjustUP(HPDataType* arr, int child)
}//向上调整数据
AdjustUP(HPDataType* arr, int child)
{//这里不需要传HP*类型的，我们可以直接通过数组下标调整就可以了，更加方便//当前结点父结点int parent = (child - 1) / 2;while (child > 0){// > 大堆// < 小堆if (arr[child] > arr[parent]){//当前结点较大进行交换Swap(&arr[child], &arr[parent]);//往上面走//孩子结点走到父结点的位置child = parent;//走到新的父结点parent = (child - 1) / 2;}else{//提前跳出循环break;}}
}

说明：

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(我们知道时间复杂度本来看的是近似值，所以多几个结点不影响最终结果)

由此可得：向上调整算法建堆时间复杂度为： O(n ∗ log2 n)

向下算法进行建堆

//1.向下的算法建堆
//child = sz - 1(最大的孩子结点下标）
//parent = （ sz - 1 - 1)/2  (最大的父结点下标）
int i = 0;
for (i = (sz - 1 - 1) / 2; i >= 0;i--)
{AdjustDown(arr, i, sz);//AdjustDown参数//AdjustDown(HPDataType* arr, int parent, int size)
}//向下调整数据
AdjustDown(HPDataType* arr, int parent, int size)
{assert(arr);//当前父结点的左孩子结点int child = 2 * parent + 1;while (child < size)//左孩子结点编号必须小于结点个数{//如果右孩子结点存在!!!// 并且右孩子结点>左孩子结点，那么child就是右孩子结点编号if (child + 1 < size && (arr[child + 1] > arr[child])){child++;}//如果父结点小于孩子结点就进行交换if (arr[parent] < arr[child]){Swap(&arr[parent], &arr[child]);//继续往下面调整parent = child;child = 2 * parent + 1;}//如果父结点大于孩子结点就提前结束循环else{break;}}
}

发现

通过上面的分析，我们可以得出

向上调整算法建堆时间复杂度为： O(n ∗ log2 n)，向下调整算法建堆时间复杂度为： O(n)