堆的数组实现
目录
2.堆是用数组实现的，在数组中通过双亲找自己左右孩子、通过左右孩子找自己双亲的思路
(1)已知左孩子下标leftchild或者右孩子下标rightchild的值，则双亲的下标公式
(2)已知孩子下标child但是不知这个孩子下标child是左孩子下标还是右孩子下标，则双亲的下标公式
1.2.再对堆尾部新插入一个数据后还有做什么操作才能让完全二叉树一直保持是个堆的分析过程
1.堆的构建函数HeapCreate与堆的初始化函数HeapInit的区别
2. 建堆函数HeapCreate利用主调函数给的数组中的数据进行建堆的三种方法
②在方法二的建堆函数HeapCreate中，利用向下调整函数AdjustDown把指针php->a指向的动态数组变成大堆的案例
③在方法二的建堆函数HeapCreate中，利用向下调整函数AdjustDown把指针php->a指向的动态数组变成堆的原理
④对利用方式二的向下调整函数建堆的时间复杂度是O(N)进行分析
⑤分析利用向下调整函数AdjustDown建堆的时间复杂度是O(N)的原因
③对利用向上调整函数建大堆的时间复杂度是O(N*logN)进行解析
1.堆排序函数HeapSort(int* a, int n)的作用
2.1.方式一：创建1个数据结构堆，不改变主调函数给的原数组的内容而是通过堆把原数组升序的结果打印出来。
2.2.方式二：不创建数据结构堆，而是直接把主调函数给的原数组创建成堆，然后在进行排序。
一、堆
二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
堆的概念及结构
1.概念
堆实际是一个完全二叉树。完全二叉树是一个前n-1层是满的而最后一层可以不满但是最后一层所有结点必须是从左到右连续不间断的的二叉树。由于满二叉树是特殊的完全二叉树，所以堆也有可能是满二叉树。注意：并不是说所有的完全二叉树都是堆，只有那些满足大堆、小堆特性的完全二叉树才能算作堆。
2.堆的分类
(1)大堆
概念：完全二叉树中的所有双亲结点存放的数据data的值都大于等于自己孩子结点中存放的数据data的值。
①大堆的详细解析：若双亲结点有两个孩子结点则这个双亲结点存放的数据data的值都大于等于自己两个孩子结点中存放的数据data的值(注意:大堆没有说明这两个孩子结点中存放的值谁大谁小)。若双亲结点只有一个孩子结点则这个双亲结点中存放的值就大于等于这一个孩子结点中存放的值。
②大堆逻辑结构的图形解析：从以下大堆的逻辑结构图中可以看到大堆即完全二叉树的所有双亲结点中存放的数据data的值都比自己左右孩子结点中存放的数据data的值要大。
③堆用数组实现时大堆的物理结构是个数组，图形解析如下：
注意：虽然在逻辑结构上看堆是个完全二叉树，但是堆在利用数组实现时把这个数组当成一颗完全二叉树，则此时这个大堆在物理内存中实际存储在一个数组当中的；堆在利用数组实现时，这个完全二叉树(指大堆)的物理结构是数组。
(2)小堆
概念：完全二叉树中的所有双亲结点存放的数据data的值都小于等于自己孩子结点中存放的数据data的值。
①小堆逻辑结构的图形解析：从以下小堆的逻辑结构图中可以看到小堆即完全二叉树的所有双亲结点中存放的数据data的值都比自己左右孩子结点中存放的数据data的值要小。
②堆在利用数组实现时小堆物理结构是个数组，图形解析如下：
注意：虽然在逻辑结构上看堆是个完全二叉树但是堆在利用数组实现时把数组当成一颗完全二叉树，则此时这个小堆在物理内存中实际存储在一个数组当中的；堆在利用数组实现时，这个完全二叉树(指小堆)的物理结构是数组)
二、利用数组(顺序结构)实现堆的过程
注意：由于用数组实现堆时只是把完全二叉树结点中存放的值存入数组中，所有在利用数组实现堆时就没有必要定义完全二叉树结点的结构体类型，只需定义完全二叉树存放数据的类型，而且数组元素的类型和完全二叉树的数据类型是一样的。在下面的描述中我们把双亲结点存放在数组中的数据data简称双亲，而孩子结点存放在数组中的数据data简称为孩子。
1.利用数组实现堆的思路
把完全二叉树每一层结点中存放的数据data按照从上到下且从左到右的顺序一层一层的存储到数组中。
2.堆是用数组实现的，在数组中通过双亲找自己左右孩子、通过左右孩子找自己双亲的思路
2.1.思路
用左右孩子下标和双亲下标在数组中的下标关系公式，就可以通过双亲下标找到自己左右孩子下标进而找到左右孩子在数组中的值，或者是通过左右孩子的下标找到自己双亲的下标进而找到双亲在数组中的值。
2.2.孩子与自己双亲的下标关系公式
注意：parent表示双亲下标、leftchild表示左孩子下标、 rightchild表示右孩子下标。
2.2.1已知双亲下标parent值，则左右孩子的下标公式
①关系公式：leftchild = 2*parent + 1 ——> 解析：左孩子下标 = 2*父亲下标 + 1。
②关系公式2：rightchild = 2*parent + 2 ——> 解析：右孩子下标 = 2*父亲下标 + 2。
图形解析：例如找双亲下标parent = 2的左右孩子下标的过程。注意：若右孩子下标超出数组的有效范围则说明当前双亲不存在右孩子。完全二叉树中每个双亲的左右孩子都是连续存储在数组中的而且左孩子的下标一定比右孩子的下标小1。
2.2.2
注意事项：
①规律：每个双亲的左孩子下标一定是奇数，双亲的右孩子下标一定是偶数。
图形解析：通过下面大堆可以看到双亲的左孩子下标在数组中是奇数，而双亲的右孩子下标在数组中是偶数。
(1)已知左孩子下标leftchild或者右孩子下标rightchild的值，则双亲的下标公式
①已知左孩子下标求双亲下标的公式：parent = (leftchild – 1) / 2。
②已知右孩子下标求双亲下标的公式：parent = (rightchild – 2) / 2。
(2)已知孩子下标child但是不知这个孩子下标child是左孩子下标还是右孩子下标，则双亲的下标公式
注意事项：
①即使child是右孩子下标而且child是个偶数导致(child - 1) / 2会出现小数，但是公式中parent = (child - 1) / 2的双亲下标parent的类型是整形int，所以双亲下标parent的值最终只保留小数(child - 1) / 2的整数部分而去掉小数部分；②由于parent的类型是整形int，导致无论孩子下标child是左孩子下标还是右孩子下标，最终通过公式parent = (child - 1) / 2计算得到的双亲下标parent的值都是一样的。
图形解析：已知孩子下标child = rightchild，利用公式parent = (child - 1) / 2 求双亲下标parent的值。
已知孩子下标child求双亲下标的统一公式：parent = (child - 1) / 2。(注意：child可能是左孩子下标leftchild，也有可能是右孩子下标rightchild)
3.总结
(1)由于我们可以随便把一个数组当成一个完全二叉树，但是不是所有的完全二叉树都是堆，而且只有那些符合大堆或者小堆特征的完全二叉树才是堆，所以我们才说不是随便一个数组就是堆，只有满足大堆小堆特性的数组才是堆。
(2)堆不一定有序，只是堆有可能有序。
(3)练习题1
①该题的解法：把下面选项出现的数字序列当成一个数组，再把这个数组写成一个完全二叉树，若这个完全二叉树符合大堆或者小堆的特征，则说明这个数组就是个堆，进而可以推导出选项中那个数字序列是个堆。
②注意事项：把数组中的数字序列画成堆(即完全二叉树)的思路：通过堆在用数组实现时是把完全二叉树一层一层结点中存放的数据按照从上到下且从左到右连续存入数组中的特性 和 双亲与孩子的下标关系公式就可以把数组画出完全二叉树(即堆)。
③小结：任何一个数组都可以看作是一个完全二叉树而且都可以把数组画出一个完全二叉树，但是不是说画出的所有完全二叉树都是堆，只有那些符合大堆小堆特性的完全二叉树才能算作堆，所以选项中的数字序列在画出完全二叉树之后再去判断这个画出的完全二叉树是否符合大堆小堆的特性我们才能确定数字序列是否是个堆。(注意：大堆小堆的特性指的是大堆的所有双亲都大于或等于自己的左右孩子，而小堆的所有双亲都小于或等于自己的左右孩子)
三、利用数组实现堆——对堆的各个功能函数进行解析
(下面的各个功能函数是)
注意：
①堆的底层是个符合大堆或者小堆特征的完全二叉树，而且利用数组实现堆的本质是要实现符合大堆或者小堆特征的完全二叉树。
②用链式结构实现堆(完全二叉树)时远不如利用数组实现堆方便，因为利用链式结构实现堆时若对堆进行尾部插入数据或者删除堆顶元素后难以保持链式结构依然是个堆。但是利用数组实现堆时，即使对堆进行尾部插入数据或者删除堆顶元素都可以通过向上调整函数和向下调整函数保持数组依然是个堆。(注意：向上调整函数和向下调整函数在下面会讲到)
③利用数组实现堆的难点在于：由于堆的逻辑结构是个完全二叉树而堆的实际物理结构是个数组，但是我们要对堆进行各种功能操作时必须把这个数组想象成一个完全二叉树进行堆的各种功能操作。
④堆的结构体类型
//堆(完全二叉树、满二叉树)存放的数据类型
typedef int HeapDataType;
//堆的结构体类型
typedef struct Heap
{
HeapDataType* a;//指针a指向堆中数据存放的动态空间
int size;//统计堆中已经存放数据个数
int capacity;//堆中用于存放数据的空间容量
}HP;堆初始化函数HeapInit
1.对主调函数中的堆hp进行初始化有两个方式
(1)方式1：开辟一块动态数组的空间并让堆hp的结构体成员变量指针a指向这块新开辟数组动态空间。
//堆初始化函数->把堆初始化为空堆。
void HeapInit(HP* php)
{
//判断指针php是否是空指针
assert(php);
//1.把堆hp初始化为空堆
//1.1动态开辟空间并让堆hp的成员变量指针a指向该空间。
php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * 4);
if (php->a == NULL)
{
perror("malloc fail");
exit(-1);
}
//1.2.把堆hp的成员变量size初始化为0表示堆hp被初始化为空堆。
php->size = 0;
php->capacity = 4;
}(1)方式2：不开辟动态数组的空间，直接把堆hp的结构体成员变量指针a的值设置为NULL。
//堆初始化函数->把堆初始化为空堆。
void HeapInit(HP* php)
{
//判断指针php是否是空指针
assert(php);
//把堆hp初始化为空堆
php->a = NULL;
//size表示堆hp中已经存放的数据个数、capacity表示堆hp中用于存放数据的空间容量
php->size = php->capacity = 0;
}
堆插入函数HeapPush
1.对堆进行插入数据的分析过程
1.1.对堆在数组中的什么位置进行插入数据的分析过程
由于完全二叉树(即堆)的前n – 1层是满的，而最后一层可以不满而且最后一层的所有数据必须是从左到右连续不间断的，导致完全二叉树只能在最后一层进行插入数据而且这个数据必须与最后一层的其他数据连续在一起，所以用数组来实现堆时导致只能在数组尾部(注意：数组的尾部是下标为size的位置)进行插入数据的操作进而代替对完全二叉树(堆)进行插入数据的操作。
1.2.再对堆尾部新插入一个数据后还有做什么操作才能让完全二叉树一直保持是个堆的分析过程
注意：虽然我们控制的是数组但是我们要把这个数组想象成完全二叉树进行各个功能函数的操作，在这里就要把数组想象成一个完全二叉树，然后在完全二叉树的尾部插入数据，而且还有考虑插入数据后这个完全二叉树是否依然操持是个堆，若不是堆了那想象一下对完全二叉树进行什么操作才能把插入数据后的完全二叉树变成堆。
(1)在堆尾部插入数据后出现的问题及对应的解决办法
一开始这个数组是个堆，但再对这个数组尾部插入一个新数据后由于这个新插入的数据的大小可能 会影响到它和它所有祖先之间的关系是否符合大堆或者小堆的特性，从而使得这个数组在新插入一个数据后有可能这个数据不符合大堆或者小堆的特性使得这个数组变成不是堆，所以我们在完成对数组进行插入新数据后一定要对新插入的数据进行向上调整的操作使得数组无论是插入前还是插入后都依然保持一直是个堆。(注意：在数组的尾部这个地方插入一个数据只会影响这个插入数据的所有祖先即相当于影响插入数据到整个完全二叉树的根之间的路径中的所有数据(注意：这里的根指的是没有父亲的根))
(2)在堆尾部插入数据的案例
①案例1：以下大堆在插入数据12后不需要对插入数据12进行向上调整的操作的原因：在对数组的尾部进行插入数据之前由于这个数组在写成完全二叉树后可以发现这个数组原来是个大堆；在对数组插入数据12后，由于这个插入数据12和自己的双亲30的大小关系是满足大堆的特性的，所以插入数据12是不需要在完全二叉树中进行向上操作的。
图形解析：
②案例2：以下大堆在插入数据100后必须要对插入数据100进行向上调整的操作的原因：在对数组的尾部进行插入数据之前由于这个数组在写成完全二叉树后可以发现这个数组原来是个大堆；在对数组插入数据100后，由于这个插入数据100和自己的双亲30的大小关系是不满足大堆的特性，而且插入数据100和自己祖先70的大小关系也是不满足大堆的特性的，最终导致插入数据100要在完全二叉树进行两次向上调整的操作。
图形解析：
2.在堆尾部插入数据的思路
图形解析：先插入一个100到数组的尾上，再进行向上调整算法，直到满足大堆。
3.代码
代码思路：在数组尾部(即堆尾部)插入数据之前要检查数组的容量是否充足，若不足则要进行扩容。在数组尾部插入数据后，不管这个数组现在是不是堆都直接利用向上调整函数AdjustUp对新插入数据进行向上调整操作，这样就可以保证数组在插入数据前后依然操持是个堆。
//交换函数
void Swap(HeapDataType* p1, HeapDataType* p2)
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//大堆的向上调整函数(注意：大堆的向上调整操作只能使用与大堆)
void AdjustUp(HeapDataType* a, int child)//形参：数组a的地址、孩子下标child。
{
//判断指针a是否是空指针
assert(a);
//找当前孩子(新插入元素)的双亲下标
int parent = (child - 1) / 2;
while (child > 0)//最多当child = 0时，while循环肯定结束。
{
if (a[child] > a[parent])//若当前孩子(新插入元素)比双亲还要大，则孩子(新插入元素)要进行向上调整。
{
//孩子(新插入元素)进行向上调整的过程：
//1.双亲和孩子(新插入元素)的值进行交换
Swap(&a[child], &a[parent]);
//2.更新孩子下标和双亲下标的值
//2.1.双亲和孩子(新插入元素)交换完后，更新孩子下标child的值，使得child始终指向新插入元素。
child = parent;
//2.2.更新双亲下标parent的值，使得parent指向此时下标child位置的新插入元素的双亲
parent = (child - 1) / 2;
}
else
break;
}
}
//堆插入函数
//注意：数组在插入数据后要依然保持数组是一个堆。
void HeapPush(HP* php, HeapDataType x)
{
//判断指针php是否是空指针
assert(php);
//判断插入位置的合法性
assert(php->size >= 0);
//在堆尾插入数据的过程：
//1.在插入之前要检查堆的容量是否充足。
if (php->size == php->capacity)
{
//若容量不足就进行扩容
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HeapDataType* tmp = (HeapDataType*)realloc(php->a,sizeof(HeapDataType) * newcapacity);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
//2.在数组尾部插入数据
php->a[php->size++] = x;//注意：插入数据x是作为最后一个孩子插入到数组尾部的。
//3.无论此时数组是否是大堆，我们都利用向上调整函数保持数组依然是个大堆。
AdjustUp(php->a, php->size - 1);//对新插入元x进行向上调整。
}大堆的向上调整函数AdjustUp
1.大堆的向上调整函数AdjustUp的思路步骤
注意事项->向上调整算法有一个前提：除了最后一个孩子，其余结点所组成的完全二叉树是个堆，则此时才能通过对最后一个孩子进行向上调整才可以把整个完全二叉树变成堆。
①向上调整：从新插入元素位置或者说从最后一个孩子开始，比较新插入元素与父结点的值。
②交换：在最大堆中，如果新插入元素的值大于其父结点的值，则交换它们的位置。
③重复步骤2和3：继续向上比较和交换，直到新插入元素到达堆顶或其父结点的值大于或等于新插入元素的值为止。
2.向上调整的作用
现在我们给出一个数组，逻辑把这个数组看做是一棵完全二叉树。我们通过从最后一个孩子开始的向上调整算法可以把完全二叉树调整成一个堆。
3.代码
//交换函数
void Swap(HeapDataType* p1, HeapDataType* p2)
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//大堆的向上调整函数(注意：大堆的向上调整操作只能使用与大堆)
void AdjustUp(HeapDataType* a, int child)//形参：数组a的地址、孩子下标child。
{
//判断指针a是否是空指针
assert(a);
//找当前孩子(新插入元素)的双亲下标
int parent = (child - 1) / 2;
while (child > 0)//最多当child = 0时，while循环肯定结束。
{
if (a[child] > a[parent])//若当前孩子(新插入元素)比双亲还要大，则孩子(新插入元素)要进行向上调整。
{
//孩子(新插入元素)进行向上调整的过程：
//1.双亲和孩子(新插入元素)的值进行交换
Swap(&a[child], &a[parent]);
//2.更新孩子下标和双亲下标的值
//2.1.双亲和孩子(新插入元素)交换完后，更新孩子下标child的值，使得child始终指向新插入元素。
child = parent;
//2.2.更新双亲下标parent的值，使得parent指向此时下标child位置的新插入元素的双亲
parent = (child - 1) / 2;
}
else
break;
}
}4.代码分析
(1)while(child > 0)循环不用双亲parent >=0来判断反而用孩子child >0来判断什么时候插入数据才会停止向上调整的操作的原因
若把while(child > 0)写成while(parent >=0)，在插入的数据比自己所有祖先都要大的这种最坏的情况下，parent有两次机会等于0。即第一次parent = 0而child != 0进入while(parent >=0)循环内部时由于if语句的判断表达式a[child]> a[parent]为真使得让孩子发生向上调整，之后通过child = parent 和parent = (child - 1) / 2使得parent = 0而child = 0。当第二次parent = 0而child = 0进入while(parent >=0)循环内部时由于if语句的判断表达式a[child]> a[parent]为假，使得异常的终止了孩子的向上调整操作。总的来说，不是说while循环用双亲parent >=0判断表示式来终止向上调整操作有什么错，而是这种终止不是正常的终止而是异常的终止，是通过第二次parent = 0且child = 0的这种情况下终止孩子的向上调整操作的。
图形解析：
删除堆顶元素函数HeapPop
注意：想要删除堆顶数据并不是直接通过挪动数组的数据覆盖掉数组头部数据来完成删除堆顶数据的操作。
1.堆不通过挪动数组元素来删除堆顶元素的分析过程
(1)通过挪动数组元素来删除堆顶元素的两大缺陷
①效率低：如果通过挪动数组元素来删除堆顶元素，那么删除操作的时间复杂度将是O(n)，因为需要将堆顶之后的所有元素向前移动一个位置。对于大型数据集来说，这种操作效率非常低。
②改变结构：堆是一个完全二叉树，如果直接删除堆顶元素，然后移动所有元素，虽然可以保持数组的连续性，但却不能保证剩下的部分仍然满足堆的性质。
2.删除堆顶元素的思路
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
3.代码
//交换函数
void Swap(HeapDataType* p1, HeapDataType* p2)
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//大堆的向下调整函数
void AdjustDown(HeapDataType* a, int n, int parent)//形参：数组a的地址、数组a的元素个数n、双亲下标parent
{
//判断指针a是否是空指针
assert(a);
//找当前双亲的左孩子下标
int child = parent * 2 + 1;//假设左孩子是最大的孩子
//注意：
//1.向下调整函数是对双亲进行向下调整而且是通过让双亲与左右孩子中最大的孩子进行比价，若双亲比最大的孩子还要小则通过交换双亲和孩子之间的值达到双亲往下调整的操作。
//2.由于此时child是左右孩子其中一个孩子的下标，所以while循环的判断表达式只能写成child < n，而不是写成child + 1 < n.
while (child < n)
{
//由于此时child指向左孩子，但是双亲可能没有右孩子，所以if语句的判断表达式中要加child + 1 < n是否为真以此来判断当前双亲是否有右孩子。若右孩子下标child + 1 > n，则说明当前双亲没有右孩子，则此时当前双亲最大孩子下标就是左孩子下标child。
if (child + 1 < n && a[child + 1] > a[child])//判断左孩子是否是最大的孩子，并让child始终指向左右孩子中最大的孩子
child++;
if (a[child] > a[parent])//若当前双亲比最大的孩子还要小，则要交换双亲和孩子的值。
{
//向下调整的过程：
//1.双亲和孩子的值进行交换
Swap(&a[child], &a[parent]);
//2.更新双亲和孩子下标的值
//2.1.双亲和孩子交换完后，更新双亲下标parent的值，使得parent指向新双亲
parent = child;
//2.2.更新孩子下标child的值，使得child指向新双亲的左孩子
child = parent * 2 + 1;//假设此时双亲的左孩子是最大的孩子;
}
else
break;
}
}
//删除堆顶元素函数。
//注意：删除堆顶元素后要保持数组依然个堆。
void HeapPop(HP* php)
{
//判断指针php是否是空指针
assert(php);
//判断堆中是否还有可以删除的元素或者说判断堆是否是个空堆。
assert(php->size > 0);
//删除堆顶元素的过程：
//1.交换堆顶元素与堆尾元素的值
Swap(&php->a[0], &php->a[php->size - 1]);
//2.通过php->size--表示删除此时位于堆尾位置的堆顶元素
php->size--;
//3.利用向下调整函数保持数组依然是个大堆
AdjustDown(php->a, php->size, 0);//对堆顶元素进行线向下调整操作
}
4.代码分析
(1)对Swap(&php->a[0]，&php->a[php->size - 1])进行解析
利用swap函数把完全二叉树的最后一个孩子的值和堆顶元素(即完全二叉树的根)的值进行交换。
(2)对php->size--代码进行解析
由于通过swap函数把完全二叉树的最后一个孩子的值和堆顶元素(即完全二叉树的根)之间的值进行交换完后，使得完全二叉树原来的最后一个孩子位于堆顶位置即数组下标为0的位置，而完全二叉树原来的堆顶元素位于数组尾部下标为size – 1的位置而且堆是用数组(即顺序表)实现的，所以通过只需通过size--的操作就可以删除堆的堆顶数据。
(3)对AdjustDown(php->a,php->size,0)代码进行解析
在把最后一个孩子和堆顶元素之间的值进行交换完后，然后利用AdjustDown(php->a,php->size,0)把处于堆顶位置(即完全二叉树根的位置)的完全二叉树最后一个孩子进行向下调整操作。
注意：AdjustDown函数的参数php->size表示的是指针php->a指向的数组中存储有效数据的个数，AdjustDown函数中的参数0表示的是最后一个子孙在堆顶位置的下标(即参数0表示的是完全二叉树根的位置)。
(4)对堆进行删除数据时规定只能删除堆顶的元素，而且除堆顶外删除堆的其他位置是没有意义的。
大堆的向下调整函数AdjustDown
1.大堆的向下调整函数AdjustDown思路
(1)向下调整的思路步骤
向下调整的注意事项->向下调整算法有一个前提：除了整棵完全二叉树的根结点外，整棵完全二叉树的左右子树必须是一个堆，才能通过对根结点进行向下调整把整个完全二叉树变成一个堆。
①向下调整：从堆顶开始，比较当前结点与其左右孩子结点的值，并找到左右孩子中的最大值。
②交换：在大堆中，如果当前结点的值小于其子结点的最大值，则当前结点与该子结点交换位置。
③重复步骤1和2：继续向下比较和交换，直到当前结点没有子结点或它的值大于其所有子结点的值为止。
(2)向下调整的作用
现在我们给出一个数组，逻辑把这个数组看做是一棵完全二叉树。我们通过从根结点开始的向下调整算法可以把完全二叉树调整成一个堆。
2.代码
//大堆的向下调整函数
void AdjustDown(HeapDataType* a, int n, int parent)//形参：数组a的地址、数组a的元素个数n、双亲下标parent
{
//判断指针a是否是空指针
assert(a);
//找当前双亲的左孩子下标
int child = parent * 2 + 1;//假设左孩子是最大的孩子
//注意：
//1.向下调整函数是对双亲(即堆顶元素)进行向下调整而且是通过让双亲(堆顶元素)与自己左右孩子中最大的孩子进行比较，若双亲(堆顶元素)比最大的孩子还要小则通过交换双亲(堆顶元素)和孩子之间的值达到让双亲(堆顶元素)往下调整的操作。
//2.由于此时child是左右孩子其中一个孩子的下标，所以while循环的判断表达式只能写成child < n，而不是写成child + 1 < n.
while (child < n)//在最坏的情况下当child = n时就必须让双亲停止向下调整操作。
{
//由于此时child指向左孩子，但是双亲(堆顶元素)可能没有右孩子，所以if语句的判断表达式中要加child + 1 < n是否为真以此来判断当前双亲(堆顶元素)是否有右孩子。若右孩子下标child + 1 > n，则说明当前双亲(堆顶元素)没有右孩子，则此时当前双亲(堆顶元素)最大孩子下标就是左孩子下标child。
if (child + 1 < n && a[child + 1] > a[child])//判断左孩子是否是最大的孩子，并让child始终指向左右孩子中最大的孩子
child++;
if (a[child] > a[parent])//若当前双亲(堆顶元素)比最大的孩子还要小，则要交换双亲(堆顶元素)和孩子的值。
{
//向下调整的过程：
//1.双亲(堆顶元素)和孩子的值进行交换
Swap(&a[child], &a[parent]);
//2.更新双亲和孩子下标的值
//2.1.双亲和孩子交换完后，更新双亲下标parent的值，使得parent始终指向堆顶元素，而且堆顶元素始终作为一个双亲结点。
parent = child;
//2.2.更新孩子下标child的值，使得child指向此时parent位置的堆顶元素的左孩子
child = parent * 2 + 1;//假设此时双亲(堆顶元素)的左孩子是最大的孩子;
}
else
break;
}
}
3.代码分析
(1)对int child = parent * 2 + 1代码进行解析：
注意：①该AdjustDown函数的内部不定义左孩子下标leftchild和右孩子下标rightchild，而是利用假设法来求出当前双亲(堆顶元素)的左右孩子中的最大值；②child永远表示当前双亲(堆顶元素)的左右孩子中的最大孩子下标。
假设法——先假设双亲(堆顶元素)的左右孩子中的最大值是左孩子，用下标child表示当前双亲(堆顶元素)的左右孩子中最大孩子的下标 ，并用公式child = parent * 2 + 1求出左孩子下标child的值。
(2)对while(child < n)中的判断表达式child < n进行分析：
在最坏的情况下堆顶元素来到完全二叉树叶结点位置，当child >= n时表示的是下标child超出数组的范围说明当前双亲(堆顶元素)的左孩子不存在，由于当前双亲(堆顶元素)的左孩子不存在可知当前双亲(堆顶元素)的右孩子一定不存在，同时说明当前这个双亲(堆顶元素)来到完全二叉树叶结点位置，则此时必须让双亲(堆顶元素)停止向下调整操作。
(3)对if(child+1 <n && a[child+1] > a[child]) ++child代码进行解析：
注意：由于child表示的是当前双亲的左右孩子中最大孩子的下标，所以if语句的功能是确定child最终表示当前双亲两个孩子中的那个孩子的下标。
利用if(child+1 <n && a[child+1] > a[child]) ++child语句来判断之前假设左孩子是最大的孩子(且用child表示左孩子的下标)是否成立，若不成立则需用++child使得此时child表示当前双亲右孩子的下标而且右孩子是双亲两个孩子中最大的一个。
(4)要想使用向下调整函数void AdjustDown(HPDataType* a, int n, int parent)对下标parent位置的堆顶元素进行向下调整操作后可以让完全二叉树变成堆的前提是下标parent位置的堆顶元素的左右子树必须是统一为大堆或者统一为小堆。若下标parent位置的堆顶元素的左右子树不是统一的大堆或小堆的话即使调用向下调整函数AdjustDown也不会让整个完全二叉树变成大堆或者小堆。
例①：堆顶元素18进行向下调整
例②：堆顶元素18进行向下调整
总的来说，除了整棵完全二叉树的根结点外，整棵完全二叉树的左右子树必须是统一的大堆或者统一的小堆，才能通过对根结点进行向下调整把整个完全二叉树变成一个大堆或者小堆。
4.总结
如果堆的各个功能函数要实现的功能会把完全二叉树从原来是个堆变成不是堆，则此时需要在各个功能函数的内部利用向下调整函数AdjustDown或者是利用向上调整函数AdjustUp让原来的完全二叉树不管被功能函数进行什么样功能操作后还能把完全二叉树一直保持是个堆。向下调整函数AdjustDown主要处理的是对双亲(堆顶元素)进行向下调整的操作，而向上调整函数AdjustUp主要处理的是对孩子(新插入元素)进行向上调整的操作。
取堆顶元素函数HeapTop
1.HeapTop函数的作用
由于堆是个完全二叉树，大堆堆顶元素是整个完全二叉树中所有元素的最大值，小堆堆顶元素是整个完全二叉树中所有元素的最小值，所以利用HeapTop函数取堆顶元素时取的是完全二叉树(堆)中所有元素的最大值或者最小值。
2.代码
//取堆顶元素(注意：大堆堆顶元素是整个堆中的最大值、小堆堆顶元素是整个小堆中的最大值)
HeapDataType HeapTop(HP* php)
{
//判断指针php是否是空指针
assert(php);
//判断堆中是否还有元素，若没有元素则不用取堆顶元素
assert(php->size > 0);
//取堆顶元素
return php->a[0];
}创建n个元素的堆函数HeapCreate
1.堆的构建函数HeapCreate与堆的初始化函数HeapInit的区别
初始化函数HeapInit的作用是：把堆hp初始化为空堆hp，不管是否为堆hp的结构体成员变量指针a分配动态空间，只要堆hp的结构体成员变量size被初始化为0就表示堆hp被初始化为空堆。
堆的构建函数HeapCreate的作用是：由于堆创建函数HeapCreate需要利用主调函数给出数组(注意：假设数组大小为n)中数据把空堆hp初始化大小为n的非空堆hp，所有在初始化之前必须要给堆hp的结构体成员变量指针a分配n个数组元素大小的动态空间。注意：虽然数组可以看成一个完全二叉树，但是并不是所有的完全二叉树都是堆，所以在利用数组元素把空堆hp初始化为大小为n的非空堆hp时一定要利用向上调整函数或者向下调整函数来保持堆hp的成员变量指针a指向的动态数组一直是个堆。
2. 建堆函数HeapCreate利用主调函数给的数组中的数据进行建堆的三种方法
(1)方法一：利用插入函数建堆
直接调用HeapPush插入函数把主调函数给的数组中的所有数据都插入到空堆hp中。
代码
(注：方式一的时间复杂度是O(N*logN)和空间复杂度是O(N))
以下是建大堆的代码：
//把空堆hp创建成n个元素的堆hp的写法1：时间复杂度O(N*logN)。
void HeapCreate(HP* php, HeapDataType* a, int n)
{
//判断指着php是否是空指针
assert(php);
//把堆hp初始化为空堆hp
HeapInit(php);
//通过把数组中所有的元素依次插入指针php指向的堆hp中，从而创建n个元素的堆hp。
for (int i = 0; i < n; i++)
{
HeapPush(php, a[i]);
}
}(2)方法二：利用向下调整函数建堆
利用向下调整函数建堆的思路：先利用memcpy把主调函数给的数组中的所有数据复制到指针php->a指向的动态数组中，然后利用向下调整函数AdjustDown从完全二叉树(即动态数组)的最后一个孩子的双亲开始按顺序从右往左再从下往上的把完全二叉树的每个双亲都进行向下调整操作直到完全二叉树的堆顶元素完成向下调整操作后才停止双亲进行向下调整操作。通过这样就可以把指针php->a指向的动态数组变成堆。
①代码
(注意：方式②的时间复杂度是O(N)和空间复杂度是O(N)；方式②是被要求不能用HeapPush函数建堆)
以下是建大堆的代码：
//交换两个元素的函数
void Swap(HeapDataType* p1, HeapDataType* p2)//形参：数组a中两个元素要发生值交换的两个元素的地址p1、p2.
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//大堆的向下调整函数
void AdjustDown(HeapDataType* a, int n, int parent)//形参：数组a的地址、数组a的元素个数n、双亲下标parent
{
//判断指针a是否是空指针
assert(a);
//找当前双亲的左孩子下标
int child = parent * 2 + 1;//假设左孩子是最大的孩子
//注意：
//1.向下调整函数是对双亲(即堆顶元素)进行向下调整而且是通过让双亲(堆顶元素)与自己左右孩子中最大的孩子进行比较，若双亲(堆顶元素)比最大的孩子还要小则通过交换双亲(堆顶元素)和孩子之间的值达到让双亲(堆顶元素)往下调整的操作。
//2.由于此时child是左右孩子其中一个孩子的下标，所以while循环的判断表达式只能写成child < n，而不是写成child + 1 < n.
while (child < n)//在最坏的情况下当child = n时就必须让双亲停止向下调整操作。
{
//由于此时child指向左孩子，但是双亲(堆顶元素)可能没有右孩子，所以if语句的判断表达式中要加child + 1 < n是否为真以此来判断当前双亲(堆顶元素)是否有右孩子。若右孩子下标child + 1 > n，则说明当前双亲(堆顶元素)没有右孩子，则此时当前双亲(堆顶元素)最大孩子下标就是左孩子下标child。
if (child + 1 < n && a[child + 1] > a[child])//判断左孩子是否是最大的孩子，并让child始终指向左右孩子中最大的孩子
child++;
if (a[child] > a[parent])//若当前双亲(堆顶元素)比最大的孩子还要小，则要交换双亲(堆顶元素)和孩子的值。
{
//向下调整的过程：
//1.双亲(堆顶元素)和孩子的值进行交换
Swap(&a[child], &a[parent]);
//2.更新双亲和孩子下标的值
//2.1.双亲和孩子交换完后，更新双亲下标parent的值，使得parent始终指向堆顶元素，而且堆顶元素始终作为一个双亲结点。
parent = child;
//2.2.更新孩子下标child的值，使得child指向此时parent位置的堆顶元素的左孩子
child = parent * 2 + 1;//假设此时双亲(堆顶元素)的左孩子是最大的孩子;
}
else
break;
}
}
//注意：由于在主调函数中堆的结构体hp已经创建了，所以下面HeapCreate函数的形参HP* php其实是堆hp的地址。
//把空堆hp创建成n个元素的堆hp的写法2：时间复杂度O(N)。
void HeapCreate(HP* php, HeapDataType* a, int n)//形参HeapDataType* a主调函数中给的一组数据并用这组数据创建1个堆、形参int n是这组数据元素的个数。
{
//判断指针php是否是空指针
assert(php);
//判断指针a是否是空指针
assert(a);
//把n个元素存放在数组a的写法2：创建n个元素大小的堆hp后，直接把数组a中所有元素复制到堆hp中。
php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
exit(-1);
}
//把数组a中所有元素都复制到堆hp的结构体成员变量指针a指向的动态数组中
memcpy(php->a, a, sizeof(HeapDataType) * n);
//复制完后要更新堆结构体的成员变量size、capacity的值。
php->size = php->capacity = n;
//利用向下调整来建大堆
for (int parent = (php->size - 1 - 1) / 2; parent >= 0; parent--)
{
AdjustDown(php->a, n, parent);
}
}②在方法二的建堆函数HeapCreate中，利用向下调整函数AdjustDown把指针php->a指向的动态数组变成大堆的案例
例1：在动态数组a没有变成大堆之前，一开始动态数组的元素是a[ ] = {1,3,8,5,4,6,9,2,7,10}。
图形解析：把动态数组a[ ] = {1,3,8,5,4,6,9,2,7,10}先想象成以下图形的完全二叉树，然后从完全二叉树最后一个孩子10的双亲4开始从右往左再从下往上的把完全二叉树的所有双亲进行向下调整操作直到堆顶元素1完成向下调整操作为止才结束。最终动态数组的元素是a[ ] = {10,7,9,5,4,6,8,2,1}而且这个动态数组a写成一个完全二叉树后可以看出这个完全二叉树是个大堆。
注意：以下是整个完全二叉树的所有左右子树变成大堆的执行顺序① —>② —> ③—> ④—>⑤。
例2：在动态数组a没有变成大堆之前，一开始动态数组的元素是a[ ] = {18,49,15,27,37,18,28,15,16,20,21,20,21,30,31}。
图形解析：把动态数组a[ ] = {18,49,15,27,37,18,28,15,16,20,21,20,21,30,31}先想象成以下图形的完全二叉树，然后从完全二叉树最后一个孩子31的双亲28开始从右往左再从下往上的把完全二叉树的所有双亲进行向下调整操作直到堆顶元素18完成向下调整操作为止才结束。最终动态数组的元素是a[ ] = {49,37,31,27,21,21,30,15,16,20,18,20,18,15,28}而且这个动态数组a写成一个完全二叉树后可以看出这个完全二叉树是个大堆。
注意：以下是整个完全二叉树的左右子树变成堆的执行顺序① —>② —> ③—> ④—>⑤。
③在方法二的建堆函数HeapCreate中，利用向下调整函数AdjustDown把指针php->a指向的动态数组变成堆的原理
理解角度1：
由于根的左右子树都不是堆或者根的左右子树都不是统一的大堆或者小堆，使得无法直接通过对整棵完全二叉树的根进行向下调整操作来让根的左右子树和整个完全二叉树都变成堆(注：这里的堆指的是变成统一的大堆或者统一的小堆)。但是要想让整个完全二叉树变成堆的话，可以把完全二叉树最后一个孩子到根之间的所有从小到大的左右子树从不是堆的逐渐通过向下调整函数变成堆(即把最后一个孩子所在的子树到根所在的整个完全二叉树之间的所有从小到大的左右子树统一变成大堆或者统一变成小堆)，所以此时要在HeapCreate函数的内部利用大堆的向下调整AdjustDown(php->a,n,parent)把完全二叉树最后一个孩子到根之间的所有从小到大的左右子树都统一变成大堆。(注意：parent一开始是完全二叉树最后一个孩子的双亲下标即parent=(n-1-1)/2，而且parent通过parent--不断减少进而使得parent可表示整个完全二叉树中的所有双亲下标)。
理解角度2：
当整个完全二叉树的层数超过两层且整个完全二叉树的左右子树不是同一个大堆或者小堆时，若此时要想把整个完全二叉树变成大堆，由于向下调整函数AdjustDown不一定把层数超过两层的完全二叉树变成堆而且向下调整函数AdjustDown一定可以把只有两层的完全二叉树变成堆的，所以此时需要先把位于整个完全二叉树倒数第二层最小的左右子树先变成大堆，然后在通过不断循环使用向下调整函数AdjustDown(php->a,n,parent)不断的从完全二叉树的底部开始往上的把层数越来越高的左右子树逐渐变成大堆，当向下调整函数AdjustDown(php->a,n,parent)的参数parent = 0时表示的是整个完全二叉树已经变成了个大堆了。(注：①这里的最小的子树指的是层数最低的子树；②可以通过完全二叉树的最后一个孩子的下标找到位于完全二叉树倒数第二层最小的左右子树；③向下调整函数AdjustDown(php->a,n,parent)的参数parent一开始是完全二叉树最后一个孩子的双亲下标)
③总结
当整个完全二叉树的层数超过两层时若整个完全二叉树的左右子树不是同一个大堆或者小堆时，则此时利用向下调整函数AdjustDown是无法把整个完全二叉树变成堆的；当整个完全二叉树的层数超过两层时，只有整个完全二叉树的左右子树都是大堆或者小堆才能让向下调整函数AdjustDown把整个完全二叉树变成堆。
向下调整函数一定可以把只有两层的完全二叉树变成堆的。
只有在完全二叉树的根以下的左右子树都是统一的大堆或者小堆的情况下，向下调整函数永远是通过对完全二叉树的根进行向下调整来让整个完全二叉树变成堆的。
④对利用方式二的向下调整函数建堆的时间复杂度是O(N)进行分析
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
因此：利用向下调整函数建堆的时间复杂度为O(N)。
⑤分析利用向下调整函数AdjustDown建堆的时间复杂度是O(N)的原因
完全二叉树层数低的结点少，而结点少的向向下调整次数多；完全二叉树层数高的结点多，而结点多的向下调整次数多，而且完全二叉树最后一层结点的结点总数几乎占整个完全二叉树的结点总数的一半进而导致利用向下调整函数建堆的时间复杂度低。总的来说，结点数量多的时候调整的次数少而结点少的时候调整次数多。
(3)方法三：利用向上调整函数建堆
①利用向上调整函数建堆的思路
先利用memcpy把主调函数给的数组中的所有数据复制到指针php->a指向的动态数组中，然后利用向上调整函数建堆是从整棵完全二叉树根的左孩子开始按顺序从左到右再从上到下的把完全二叉树的每个孩子都进行向上调整操作直到完全二叉树的最后一个孩子完成向上调整操作后才停止孩子进行向上调整操作。通过这样就可以把指针php->a指向的动态数组变成堆。
注意：利用向上调整建堆的思想有点类似于利用HeapPush函数把数组中的所有元素一个一个插入空堆中。
图形解析：以下是利用向上调整把堆hp的结构体成员变量指针a指向的动态数组变成大堆的过程。
②代码：
注意：①利用向上调整函数AdjustUp建堆的算法的时间复杂度是O(N*logN)和空间复杂度是O(1)；②以下代码是建大堆的。
//交换两个元素的函数
void Swap(HeapDataType* p1, HeapDataType* p2)//形参：数组a中两个元素要发生值交换的两个元素的地址p1、p2.
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//大堆的向上调整函数(注意：大堆的向上调整操作只能使用与大堆)
void AdjustUp(HeapDataType* a, int child)//形参：数组a的地址、孩子下标child。
{
//判断指针a是否是空指针
assert(a);
//找当前孩子(新插入元素)的双亲下标
int parent = (child - 1) / 2;
while (child > 0)//最多当child = 0时，while循环肯定结束。
{
if (a[child] > a[parent])//若当前孩子(新插入元素)比双亲还要大，则孩子(新插入元素)要进行向上调整。
{
//孩子(新插入元素)进行向上调整的过程：
//1.双亲和孩子(新插入元素)的值进行交换
Swap(&a[child], &a[parent]);
//2.更新孩子下标和双亲下标的值
//2.1.双亲和孩子(新插入元素)交换完后，更新孩子下标child的值，使得child始终指向新插入元素。
child = parent;
//2.2.更新双亲下标parent的值，使得parent指向此时下标child位置的新插入元素的双亲
parent = (child - 1) / 2;
}
else
break;
}
}
//注意：由于在主调函数中堆的结构体hp已经创建了，所以下面HeapCreate函数的形参HP* php其实是堆hp的地址。
//把空堆创建成n个元素的堆的写法1：时间复杂度O(N)。
void HeapCreate(HP* php, HeapDataType* a, int n)//形参HeapDataType* a主调函数中给的一组数据并用这组数据创建1个堆、形参int n是这组数据元素的个数。
{
//判断指针php是否是空指针
assert(php);
//判断指针a是否是空指针
assert(a);
//把n个元素存放在数组a的写法2：创建n个元素大小的堆后，直接把数组a中所有元素复制到堆中。
php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
exit(-1);
}
//把数组a中所有元素都复制堆中
memcpy(php->a, a, sizeof(HeapDataType) * n);
//复制完后要更新堆结构体的成员变量size、capacity的值。
php->size = php->capacity = n;
//利用向上调整来建大堆
for (int child = 1;child < n; child++)
{
AdjustUp(php->a, n, child);
}
}③对利用向上调整函数建大堆的时间复杂度是O(N*logN)进行解析
④分析向上调整函数AdjustUp建堆的时间复杂度是O(N*logN )的原因
完全二叉树层数低的结点少，而结点少的向上调整次数少；完全二叉树层数高的结点多，而结点多的向上调整次数多，而且完全二叉树最后一层结点的结点总数几乎占整个完全二叉树的结点总数的一半进而导致利用向上调整函数建堆的时间复杂度高。总的来说，结点少的调整次数少，结点多的调整次数多。
3.总结
(1)利用向下调整建堆时完全二叉树向下调整的调整特点是：
①完全二叉树最后一层的结点在数量上几乎占了完全二叉树一半的结点。
②直接跳过完全二叉树最后一层结点然后从倒数第二层的结点开始向下调整。
③由于完全二叉树越往下的层数当层的结点数量越多而且越往下的层数当层的结点可以向下移动的层数越少导致结点数量多的时候向下调整的次数少而结点少的时候向下调整次数多。(总的来说，结点少的向下调整次数多，结点少的向下调整次数少)
(2)由于用向下调整函数建堆的时间复杂度比用向上调整函数建堆的时间复杂度低，所以最好用向下调整函数建堆。
(3)之所以是从完全二叉树最后一个孩子的双亲开始进行向下调整操作来建堆的原因是:
当完全二叉树只有一个结点时则此时可以认为这个只有一个结点的完全二叉树是个堆。而整个完全二叉树的最后一个孩子和自己的双亲组成的只有两个结点的子完全二叉树的子树就是个堆，所以只需对最后一个孩子的双亲进行向下调整操作就可以让这个子完全二叉树是个堆。
堆排序函数HeapSort
1.堆排序函数HeapSort(int* a, int n)的作用
可以通过把数组建成大堆或者小堆后方便把数组排成升序或者降序。
2.把数组建成堆并进行排序的两种方式
2.1.方式一：创建1个数据结构堆，不改变主调函数给的原数组的内容而是通过堆把原数组升序的结果打印出来。
(1)思路步骤
①新创建1个数据结构大堆hp，并用主调函数给的数组中的所有数据把空堆hp初始化为n个元素大小的非空堆hp
②通过不断的利用HeapTop函数取大堆的堆顶元素并打印出来，和不断利用HeapPush函数删除大堆堆顶元素使得我们可以在不改变主调函数原数组的内容的情况下，而是通过大堆hp把原数升序的结果打印出来。
(2)代码
建大堆数据结构排升序思路：由于大堆的堆顶元素是堆中所有元素的最大值，所以我们只需不断的取堆顶元素并打印出来然后再不断的删除堆顶元素就可以利用堆打印出原数组升序的结果。
//由于上面提到了插入函数HeapPush、删除堆顶元素函数HeapPop、取堆顶元素函数HeapTop，所以下面就不展示这些函数了。
//判断堆是否是空堆
bool HeapEmpty(HP* php)
{
//判断指着php是否是空指针
assert(php);
return php->size == 0;
}
//堆销毁函数
void HeapDestroy(HP* php)
{
//判断指针php是否是空指针
assert(php);
//销毁堆hp的动态空间
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
//堆排序写法1：不改变原数组，而是直接打印原数组排序的结果
void HeapSort(int* a, int n)
{
//创建堆hp
HP hp;
//把堆hp初始化为空堆hp
HeapInit(&hp);
//利用主调函数给的数组中的所有数据把空堆hp初始化为n个元素大小的非空堆hp
for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
{
HeapPush(&hp, a[i]);
}
while (!HeapEmpty(&hp))
{
printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
HeapDestroy(&hp);
}2.2.方式二：不创建数据结构堆，而是直接把主调函数给的原数组创建成堆，然后在进行排序。
(1)在原数组建堆排序的思路步骤(以排升序为例)：
①建大堆：利用向下调整函数把原数组建成大堆。
②交换：建完大堆后，把堆顶元素和完全二叉树最后一个孩子(即堆最后一个元素)进行交换，交换完后就会使大堆中最大值(即堆顶元素)排在堆的最后面。
③减少完全二叉树可以访问的元素数量：同时交换之后我们认为此时处于堆尾位置的堆顶元素不再是堆中的元素进而使得完全二叉树元素的数量减少1。
④保持完全二叉树依然是个大堆：由于交换完后此时完全二叉树根下面的左右子树是大堆而整个完全二叉树已经不是堆了，所以此时我们要对处于堆顶位置的堆尾数据进行向下调整操作从而使得整个完全二叉树变成大堆。把完全二叉树变成大堆的目的是选出完全二叉树中次大的数放在堆顶的位置。
⑤持续次序执行步骤2、3、4直到完全二叉树只剩下一个结点没有排序为止。
总的来说，建大堆排升序的算法思路是：每次通过向下调整不断的选出位于堆顶位置的堆中所有元素的最大值，然后每次都把选出的堆顶元素和堆最后一个元素进行交换，交换后每次都认为堆最后一个元素不再是堆中的数据使得每次利用向下调整函数把非堆的完全二叉树变成堆的过程中完全二叉树的结点数量都比上一次进行向上调整操作时结点的数量少1。
图形解析：下面图形中蓝色的结点已经不认为是完全二叉树中的数据了。
(2)类型1：在原数组中建大堆排升序
代码：
//交换两个元素的函数
void swap(int* p1, int* p2)//形参：数组a中两个元素要发生值交换的两个元素的地址p1、p2.
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//建大堆的向下调整
void AdjustDown1(int* a, int n, int parent)
{
assert(a);
//找当前双亲的左孩子
int child = parent * 2 + 1;
while (child < n)
{
//让child始终指向当前双亲的左右孩子中最大一个孩子
if (child + 1 < n && a[child + 1] > a[child])
child++;
if (a[child] > a[parent])//若当前双亲比最大一个孩子还有小，则当前双亲就要进行向下调整。
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
//建大堆，排升序
void HeapSort1(int* a, int n)
{
//判断指针a是否是空指针
assert(a);
//注意：由于利用向上调整函数建堆的时间复杂度是O(N*logN),而利用向下调整函数建堆的时间复杂度是O(N)，导致我们在建大堆是一般使用向下调整函数来建大堆的。
//1.在原数组中建大堆
//(1)利用向上调整函数建大堆。
/*int child = 0;
for (child = 1; child < n; child++)
AdjustUp1(a, child);*/
//(2)利用向下调整函数建大堆
int parent = 0;
for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)
AdjustDown1(a, n, parent);
//2.利用大堆把原数组排成升序
//思路：
int k = n - 1;//若想排好n个元素，则排序次数是k = n - 1。
while (k--)
{
//(1)交换大堆堆顶元素和堆尾元素的值
swap(&a[0], &a[n - 1]);
//(2)不把处于数组尾部的堆顶元素看作是数组元素
n--;
//(3)利用向下调整操作保持数组剩余元素依然是个大堆
AdjustDown1(a, n, 0);
}
}(2)类型2：在原数组中建小堆排降序
代码：
//交换两个元素的函数
void swap(int* p1, int* p2)//形参：数组a中两个元素要发生值交换的两个元素的地址p1、p2.
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//建小堆的向下调整
void AdjustDown2(int* a, int n, int parent)
{
assert(a);
//找当前双亲的左孩子
int child = parent * 2 + 1;
while (child < n)
{
//让child始终指向当前双亲的左右孩子中最小的那个孩子
if (child + 1 < n && a[child + 1] < a[child])
child++;
if (a[child] < a[parent])//若当前双亲比最小的孩子还有大，则当前双亲就要向下进行调整
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
//建小堆，排降序
void HeapSort2(int* a, int n)
{
//判断指针a是否是空指针
assert(a);
//注意：由于利用向上调整函数建堆的时间复杂度是O(N*logN),而利用向下调整函数建堆的时间复杂度是O(N)，导致我们在建大堆是一般使用向下调整函数来建小堆的。
//1.在原数组中建大堆
//(1)利用向上调整函数建大堆。
/*int child = 0;
for (child = 1; child < n; child++)
AdjustUp2(a, child);*/
//(2)利用向下调整函数建大堆
int parent = 0;
for (parent = (n - 1 - 1) / 2; parent >= 0; parent--)
AdjustDown2(a, n, parent);
//2.利用大堆把原数组排成升序
//思路：
int k = n - 1;//若想排好n个元素，则排序次数是k = n - 1。
while (k--)
{
//(1)交换大堆堆顶元素和堆尾元素的值
swap(&a[0], &a[n - 1]);
//(2)不把处于数组尾部的堆顶元素看作是数组元素
n--;
//(3)利用向下调整操作保持数组剩余元素依然是个大堆
AdjustDown2(a, n, 0);
}
}四、利用数组实现堆的整个工程
1.Heap.h
//Heap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
//堆的逻辑结构是完全二叉树，堆的物理结构是数组
//注意：堆也可以用链式结构实现，但是堆用链式结构实现远没有用数组实现方便，用数组实现堆只是难以想象堆(完全二叉树)的结构而已.
//堆(完全二叉树、满二叉树)存放的数据类型
typedef int HeapDataType;
//堆的结构体类型
typedef struct Heap
{
HeapDataType* a;//指针a指向堆中数据存放的动态空间
int size;//统计堆中已经存放数据个数
int capacity;//堆中用于存放数据的空间容量
}HP;
//向下调整函数
void AdjustDown(HeapDataType* a, int n, int parent);//形参：数组a的地址、数组a的元素个数n、双亲下标parent
//向上调整函数
void AdjustUp(HeapDataType* a, int child);//形参：数组a的地址、孩子下标child。注意：由于孩子是向上调整的所以无需传数组a的元素个数size给AdjustUp函数。
//交换两个元素的函数
void Swap(HeapDataType* p1, HeapDataType* p2);//形参：数组a中两个元素要发生值交换的两个元素的地址p1、p2.
//创建n个元素的堆(注意：在主调函数中堆的结构体已经创建了)
void HeapCreate(HP* php, HeapDataType* a, int n);//形参HeapDataType* a主调函数中给的一组数据并用这组数据把空堆hp创建成大小为n的非空堆hp。形参int n是这组数据元素的个数。
//堆打印函数
void HeapPrint(HP* php);
//堆初始化函数->把堆初始化为空堆。
void HeapInit(HP* php);
//堆销毁函数
void HeapDestroy(HP* php);
//堆插入函数。
void HeapPush(HP* php, HeapDataType x);
//删除堆顶元素函数。
void HeapPop(HP* php);
//取堆顶元素(注意：大堆堆顶元素是整个堆中的最大值、小堆堆顶元素是整个小堆中的最大值)
HeapDataType HeapTop(HP* php);
//统计堆中存放元素的个数
int HeapSize(HP* php);
//判断堆是否是空堆
bool HeapEmpty(HP* php);
//堆排序函数->建大堆，排升序
void HeapSort(int* a, int n);
2.Heap.c
#include "Heap.h"
//大堆的向下调整函数。时间复杂度O(N).
void AdjustDown(HeapDataType* a, int n, int parent)//形参：数组a的地址、数组a的元素个数n、双亲下标parent
{
//判断指针a是否是空指针
assert(a);
//找当前双亲的左孩子下标
int child = parent * 2 + 1;//假设左孩子是最大的孩子
//注意：
//1.向下调整函数是对双亲(即堆顶元素)进行向下调整而且是通过让双亲(堆顶元素)与自己左右孩子中最大的孩子进行比较，若双亲(堆顶元素)比最大的孩子还要小则通过交换双亲(堆顶元素)和孩子之间的值达到让双亲(堆顶元素)往下调整的操作。
//2.由于此时child是左右孩子其中一个孩子的下标，所以while循环的判断表达式只能写成child < n，而不是写成child + 1 < n.
while (child < n)//在最坏的情况下当child = n时就必须让双亲停止向下调整操作。
{
//由于此时child指向左孩子，但是双亲(堆顶元素)可能没有右孩子，所以if语句的判断表达式中要加child + 1 < n是否为真以此来判断当前双亲(堆顶元素)是否有右孩子。若右孩子下标child + 1 > n，则说明当前双亲(堆顶元素)没有右孩子，则此时当前双亲(堆顶元素)最大孩子下标就是左孩子下标child。
if (child + 1 < n && a[child + 1] > a[child])//判断左孩子是否是最大的孩子，并让child始终指向左右孩子中最大的孩子
child++;
if (a[child] > a[parent])//若当前双亲(堆顶元素)比最大的孩子还要小，则要交换双亲(堆顶元素)和孩子的值。
{
//向下调整的过程：
//1.双亲(堆顶元素)和孩子的值进行交换
Swap(&a[child], &a[parent]);
//2.更新双亲和孩子下标的值
//2.1.双亲和孩子交换完后，更新双亲下标parent的值，使得parent始终指向堆顶元素，而且堆顶元素始终作为一个双亲结点。
parent = child;
//2.2.更新孩子下标child的值，使得child指向此时parent位置的堆顶元素的左孩子
child = parent * 2 + 1;//假设此时双亲(堆顶元素)的左孩子是最大的孩子;
}
else
break;
}
}
//大堆的向上调整函数(注意：大堆的向上调整操作只能使用与大堆)。时间复杂度：O(logN)
void AdjustUp(HeapDataType* a, int child)//形参：数组a的地址、孩子下标child。
{
//判断指针a是否是空指针
assert(a);
//找当前孩子(新插入元素)的双亲下标
int parent = (child - 1) / 2;
while (child > 0)//最多当child = 0时，while循环肯定结束。
{
if (a[child] > a[parent])//若当前孩子(新插入元素)比双亲还要大，则孩子(新插入元素)要进行向上调整。
{
//孩子(新插入元素)进行向上调整的过程：
//1.双亲和孩子(新插入元素)的值进行交换
Swap(&a[child], &a[parent]);
//2.更新孩子下标和双亲下标的值
//2.1.双亲和孩子(新插入元素)交换完后，更新孩子下标child的值，使得child始终指向新插入元素。
child = parent;
//2.2.更新双亲下标parent的值，使得parent指向此时下标child位置的新插入元素的双亲
parent = (child - 1) / 2;
}
else
break;
}
}
//交换两个元素的函数
void Swap(HeapDataType* p1, HeapDataType* p2)//形参：数组a中两个元素要发生值交换的两个元素的地址p1、p2.
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//注意：由于在主调函数中堆的结构体hp已经创建了，所以下面HeapCreate函数的形参HP* php其实是堆hp的地址。
//把空堆创建成n个元素的堆的写法1：时间复杂度O(N)。
void HeapCreate(HP* php, HeapDataType* a, int n)//形参HeapDataType* a主调函数中给的一组数据并用这组数据创建1个堆、形参int n是这组数据元素的个数。
{
//判断指针php是否是空指针
assert(php);
//判断指针a是否是空指针
assert(a);
//把n个元素存放在数组a的写法2：创建n个元素大小的堆后，直接把数组a中所有元素复制到堆中。
php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * n);
if (php->a == NULL)
{
perror("malloc fail");
exit(-1);
}
//把数组a中所有元素都复制堆中
memcpy(php->a, a, sizeof(HeapDataType) * n);
//复制完后要更新堆结构体的成员变量size、capacity的值。
php->size = php->capacity = n;
//利用向下调整来建大堆
for (int parent = (php->size - 1 - 1) / 2; parent >= 0; parent--)
{
AdjustDown(php->a, n, parent);
}
}
//把空堆创建成n个元素的堆的写法2：时间复杂度O(N*logN)。
//void HeapCreate(HP* php, HeapDataType* a, int n)
//{
////判断指着php是否是空指针
//assert(php);
//
////把堆初始化为空堆
//HeapInit(php);
//
////通过把数组中所有的元素依次插入指针php指向的堆中，从而创建n个元素的堆。
//for (int i = 0; i < n; i++)
//{
//HeapPush(php, a[i]);
//}
//}
//堆打印函数
void HeapPrint(HP* php)
{
assert(php);
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
//换行
printf("\n");
}
//堆初始化函数写法1：把堆初始化为空堆。
void HeapInit(HP* php)
{
//判断指针php是否是空指针
assert(php);
//把堆hp初始化为空堆
php->a = NULL;
php->size = php->capacity = 0;
}
//堆初始化函数写法2：：把堆初始化为空堆。
//void HeapInit(HP* php)
//{
////判断指针php是否是空指针
//assert(php);
////1.把堆hp初始化为空堆
////1.1动态开辟空间并让堆hp的成员变量指针a指向该空间。
//php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * 4);
//if (php->a == NULL)
//{
//perror("malloc fail");
//exit(-1);
//}
//
////1.2.把堆hp的成员变量size初始化为0表示堆hp被初始化为空堆。
//php->size = 0;
//php->capacity = 4;
//}
//堆销毁函数
void HeapDestroy(HP* php)
{
//判断指针php是否是空指针
assert(php);
//销毁堆hp的动态空间
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
//堆插入函数->时间复杂度O(logN)
//注意：数组在插入数据后要依然保持数组是一个堆。
void HeapPush(HP* php, HeapDataType x)
{
//判断指针php是否是空指针
assert(php);
//判断插入位置的合法性
assert(php->size >= 0);
//在堆尾插入数据的过程：
//1.在插入之前要检查堆的容量是否充足。
if (php->size == php->capacity)
{
//若容量不足就进行扩容
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HeapDataType* tmp = (HeapDataType*)realloc(php->a, sizeof(HeapDataType) * newcapacity);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
//2.在数组尾部插入数据
php->a[php->size++] = x;//注意：插入数据x是作为最后一个孩子插入到数组尾部的。
//3.无论此时数组是否是大堆，我们都利用向上调整函数保持数组依然是个大堆。
AdjustUp(php->a, php->size - 1);//对新插入元x进行向上调整。
}
//删除堆顶元素函数->时间复杂度：O(N)
//注意：删除堆顶元素后要保持数组依然个堆。
void HeapPop(HP* php)
{
//判断指针php是否是空指针
assert(php);
//判断堆中是否还有可以删除的元素或者说判断堆是否是个空堆。
assert(php->size > 0);
//删除堆顶元素的过程：
//1.交换堆顶元素与堆尾元素的值
Swap(&php->a[0], &php->a[php->size - 1]);
//2.通过php->size--表示删除此时位于堆尾位置的堆顶元素
php->size--;
//3.利用向下调整函数保持数组依然是个大堆
AdjustDown(php->a, php->size, 0);//对堆顶元素进行线向下调整操作
}
//取堆顶元素(注意：大堆堆顶元素是整个堆中的最大值、小堆堆顶元素是整个小堆中的最大值)
HeapDataType HeapTop(HP* php)
{
//判断指针php是否是空指针
assert(php);
//判断堆中是否还有元素，若没有元素则不用取堆顶元素
assert(php->size > 0);
//取堆顶元素
return php->a[0];
}
//统计堆中放元素的个数
int HeapSize(HP* php)
{
//判断指着php是否是空指针
assert(php);
return php->size;
}
//判断堆是否是空堆
bool HeapEmpty(HP* php)
{
//判断指着php是否是空指针
assert(php);
return php->size == 0;
}
//堆排序写法1：时间复杂度：O(N*logN)
//建大堆排升序
void HeapSort(int* a, int n)
{
// 向上调整建堆的时间复杂度：O(N*logN)
/*for (int i = 1; i < n; ++i)
{
AdjustUp(a, i);
}*/
// 向下调整建堆的时间复杂度：O(N)
//想要把数组排成升序则就要建大堆；想要把数组排成降序则就要建小堆。
//把数组看成完全二叉树后，直接在要排序的原数组中建大堆。
for (int i = (n - 1 - 1) / 2; i >= 0; --i)//双亲下标公式parent = (child - 1) / 2 = ((n - 1) - 1) / 2，而child = n - 1。
{
AdjustDown(a, n, i);
}
//建完大堆后对数组进行排序的时间复杂度是O(N*logN)
//注意：
//1.对大堆进行堆排序的时间复杂度的计算过程和利用向上调整函数建大堆的计算过程是相似的。
//2.由于堆(完全二叉树)最后一层的结点总数几乎占了整棵树结点总数的一半，所以堆排序的时间复杂度可以只出略考虑排完完全二叉树最后一层结点的顺序所花费的时间复杂度是O(N*logN)，所以整个堆排序的时间复杂度是O(N*logN)。
//3.堆排序的时间复杂度之所以是O(N*logN)是因为：由于完全二叉树最后一层的元素个数占据整棵树结点总数的一半，所以想要排后完全二叉树最后一层元素的顺序在最后情况下的基本操作次数大于是N*logN(N表示元素个数，logN表示最坏情况下的向下调整次数)
//4.下面堆排序的实现思想有点类似于删除堆顶元素函数HeapPop的实现思想。
int end = n - 1;//end永远表示堆中最后一个数据的下标。
while (end > 0)//当end = 0时堆中要排序的元素个数是end + 1 = 0 + 1 = 1则此时堆排序就结束了。
{
Swap(&a[0], &a[end]);//由于此时大堆堆顶元素就是此时整个堆中元素的最大值，若想把数组排成升序的话则把堆顶元素与堆尾元素进行交换。交换完后通过end--认为此时在堆尾的堆顶元素已经不是堆中元素了。
//由于堆顶元素与堆尾元素交换完后导致此时的数组中end个元素组成的完全二叉树不是堆，所以此时需要对位于堆顶位置的堆尾元素进行向下调整操作。
AdjustDown(a, end, 0);//void AdjustDown(HPDataType* a, int n, int parent)
--end;//end + 1表示此时堆中存放元素个数
}
}
堆排序写法2：不改变原数组，而是直接打印排序的结果
建大堆排升序
//void HeapSort(int* a, int n)
//{
////创建堆hp
//HP hp;
////把堆hp初始化为空堆hp
//HeapInit(&hp);
//
////利用主调函数给的数组中的所有数据把空堆hp初始化为n个元素大小的非空堆hp
//for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
//{
//HeapPush(&hp, a[i]);
//}
//
//while (!HeapEmpty(&hp))
//{
//printf("%d ", HeapTop(&hp));
//HeapPop(&hp);
//}
//
//HeapDestroy(&hp);
//}原文地址：https://blog.csdn.net/2302_76314368/article/details/142523054
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！