目录
关于完全二叉树（Complete Binary Tree）的相关解释：
关于父节点大于子节点（Parent > Children）的相关解释：
在正式开始介绍堆排序之前，我们先来简单了解一下数据结构：
数据结构的简单介绍：
在严蔚敏的《数据结构（C语言版）》一书中对数据结构是这样定义的：
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素之间的关系称为结构（Structure）。根据数据元素之间关系的不同特性，通常有以下四类基本结构：
集合：
结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系；
线性结构：
结构中的数据元素之间存在一个对一个的关系；
树形结构：
结构中的数据元素存在一个对多个的关系；
图状结构或网状结构：
结构中的数据元素之间存在多个对多个的关系。
以上为四种基本结构的关系图，由于“集合” 是数据元素之间一种极为松散的结构，因此也可以用其他结构来表示。
从树形结构开始了解：
树形结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序中，可以用树来表示源程序的语法结构，或者在数据库系统中，树形结构也是信息的重要组织形式之一，关于树的详细内容我会在以后着重进行介绍，这篇文章只是会以树这种数据结构作为引子来开启堆排序的学习，接下来我将要介绍的堆排序就是以树形结构为基础的一种排序算法。
什么是堆（heap）？
注意，这里的堆不是计算机内存结构中的堆区，与堆区（Heap Area）没有关系！
我们来看看书中对堆的定义什么：
这一堆公式看起来很让人头大，我来说说我对堆的理解：
堆是计算机科学中一类特殊的数据结构的统称，通常是一个可以被看做一颗完全二叉树的数组对象。
堆是一种数据类型，要想被称之为堆，必须要具备以下两个特点：
1:是一个完全二叉树（Complete Binary Tree）
2:必须满足父节点值大于子节点值的条件（Parent > Children）
关于完全二叉树（Complete Binary Tree）的相关解释：
完全二叉树生成节点的顺序是从上往下，从左往右，以下是构建完全二叉树的几种情况：
如果此时我们要去构建完全二叉树，我们只能在第二层的最右方的节点进行添加。
如果我们此时要对这一颗二叉树添加节点的话我们只能在第三层的第一个节点处添加，也就是我用红色圈住的节点，如果在其他节点进行添加的话，它就不是完全二叉树了，如果在添加一个节点过后还想在添加一个节点，那么我们依旧从红色圈节点处在进行添加，然后再到第二个节点，依次类推，顺序不能乱，顺序乱了它就不是一颗完全二叉树。
关于父节点大于子节点（Parent > Children）的相关解释：
我们继续用上面的二叉树来进行解释：
如图，在红色方框内，父节点是5，子节点是3和2，在这个完全二叉树中5是大于它的每一个子节点的，同样，6的子节点为1和4，6大于1和4，5和6作为9的子节点，也都是小于子节点的，所以我们说上图的数据类型就是一个堆。
只有满足完全二叉树（Complete Binary Tree）和所有父节点大于子节点（Parent > children）的才能称之为 堆。
如何构建一个堆？
在前面我们说过，要形成一个堆，必须是一个完全二叉树，如果在一个完全二叉树中并不满足父节点大于子节点的关系的话，我们就要对父节点和子节点的位置进行调换，我们把这个过程称之为堆化（Heapify），例如我在这里给出一个完全二叉树，我们对它进行堆化：
假设我们现在的这颗完全二叉树里面的数据完全是乱的，我们如何对这颗完全二叉树进行堆化呢？
如图，只要是一个完全二叉树，我们就从他的h - 1层的最右子树开始heapify，然后再heapify它的左子树，一直堆化至它的最左子树，然后再向上堆化，直至堆化至顶点。
那我们如果用数组来表示一个堆的话，就要给他添加上编号，如图：
那我们就可以用一维数组来表示一颗完全二叉树，这样做的优点就是我从任意一个节点的标号出发我均可以通过计算来推理出他的父节点和子节点的标号
我们用上面的完全二叉树来举例子例如在第二层从右往左数的第一个元素6，此时它的标号是1，它的父节点的标号是0，子节点的标号分别是3和4；我们再来看元素9，他的标号是2，父节点的标号是0，子节点的标号分别是5和6，所以我们可以总结出以下的规律：
如果已知一个元素在完全二叉树中的标号（我们设定这个值为i）：
它的父节点的标号为：（i - 1）/ 2
它的子节点c1、c2的标号分别为：（2i + 1）和（2i + 2）
我们将heapify的过程代码化：
#include<stdio.h>
#include<assert.h>
void heapify(int *tree,int n,int i)//tree代表着完全二叉树，n代表着这棵树一共有多少个节点，i表示我们具体要对哪个节点进行heapify操作
{
assert(tree != NULL);
if(i >= n){//递归出口
return;
}
int c1 = 2 * i + 1;//利用公式找出i节点的第一个子节点
int c2 = 2 * i + 2;//找出i节点的第二个子节点
int max = i;
if(c1 < n && tree[c1] > tree[max]){
max = c1;
}
if(c2 < n && tree[c2] > tree[max]){
max = c2;
}
if(max != i){
swap(tree,max,i);
heapify(tree,n,max);//递归操作
}
}
int main()
{
int tree[] = {1,5,2,4,3,10};
heaping(ar,6,0);
for(int i = 0;i < n;i++){
printf("%d ",tree[i]);
}
return 0;
}运行结果：
如图，成功地完全二叉树进行了堆化并输出
如果tree中所有的数字都是乱的，我们如何构建一个堆？
我们原来的完全二叉树再添加一层树，如果我们要使上面的数据构成一个堆，那我们所要完全二叉树执行heapify的顺序应该是从下往上，从右往左依次进行的，进行完了之后，我们就构建成了一个堆
对于上面的二叉树我们所要执行的顺序就是：3->2->1->0，我们发现这些节点均是父节点，我们对这些节点对应二叉树依次进行heapify操作，即可完成堆的构建。
从上面的规律不难发现，我们要对任何一个完全二叉树进行heapify操作，我们第一个必须找到的就是最后一个节点的父节点，然后从这个节点进行heapify操作的下一步跳转至下一个节点再进行堆化操作，直到我们完成对根节点的heapify操作，对一个完全二叉树的堆化操作才算完成。
讨论如何找出一个完全二叉树的最后一个节点的父节点：
通过观察上图我们可以发现，整颗完全二叉树一共有9个节点，而最后一个节点的标号是[8]，所以最后一个节点是（n代表树中共有多少个节点）9 - 1，他的父节点的就是（（9 - 1） - 1）/ 2，这里我们通过上图来举例子，（8 - 1）/ 2就是3.5，我们定义的值为整形变量所以我们只取整数部分，就是3
所以我们得出规律：
任何一个二叉树最后一个节点的父节点值都为它最后一个节点的的标号减一再除以2
代码实现：
void build_heap(int *tree,int n)
{
int last_node = n - 1;//表示最后一个节点
int parent_node = (n - 1) / 2;//表示最后一个节点的父节点
for(int i = parent_node;i >= 0;i--){//循环heapify父节点，完成堆的构建
heapify(tree,n,i);
}
}
int main()
{
int tree[] = {1,5,2,4,3,10};
build_heap(ar,6);
for(int i = 0;i < n;i++){
printf("%d ",tree[i]);
}
return 0;
}运行结果：
我们看到生成的这样一组数据是符合堆的结构的。
我们成功构建出来一个堆之后，如何进行堆排序？
这里我们使用上面的数据来进行堆排序的演示：
这时我们可以确定，根节点10是这个堆里面最大的数，所以我们把这个最大的数和最后一个节点进行一个交换，交换完成后，我们将最后一个节点拿出来：
我们做完根节点和最后一个节点的交换之后，相当于我们破坏了堆的结构，所以我们重新对堆进行构建，我们对根节点再次做heapify操作：
于是我们又得到了一个新堆，此时我们继续将根节点5与最后一个节点进行交换，并把最后一个节点拿出来：
此时我们再次对交换之后的完全二叉树进行heapify操作：
现在我们继续将根节点与最后一个节点交换并拿出来添加到刚才那两个数字的前面：
此时我们再次进行heapify操作，并将根节点与最后一个节点进行交换并拿出来：
注意在这个过程中其实我多做了一步，我们只需要寻找这个完全二叉树中的最大值放置根节点即可。
最后我们将这个剩下的两个数直接添加即可：
如图，成功地对tree中的元素进行了升序排序。
代码实现：
#include<stdio.h>
#include<assert.h>
void heap_sort(int *tree,int n)
{
assert(tree != nullptr);
build_heap(tree,n);//调用数构建堆函数
int i = 0;
for(i = n - 1;i >= 0;i--){//循环对最后一个节点和根节点进行交换，并重构堆
swap(tree,i,0);
heapify(tree,i,0);
}
}
int main()
{
int tree[] = {4,10,3,5,1,2};
int n = 6;
heap_sort(tree,n);
for(int i = 0;i < n;i++){
printf("%d ",tree[i]);
}
return 0;
}运行结果：
如图，程序成功地将tree数组中的6个元素进行了升序排序并输出
完成程序源码：
#include<stdio.h>
#include<assert.h>
void swap(int *ar,int index1,int index2)
{
int temp = ar[index1];
ar[index1] = ar[index2];
ar[index2] = temp;
}
void heapify(int *tree,int n,int i)//tree代表着完全二叉树，n代表着这棵树一共有多少个节点，i表示我们具体要对哪个节点进行heapify操作
{
assert(tree != nullptr);
if(i >= n){//递归出口
return;
}
int c1 = 2 * i + 1;//利用公式找出i节点的第一个子节点
int c2 = 2 * i + 2;//找出i节点的第二个子节点
int max = i;
if(c1 < n && tree[c1] > tree[max]){
max = c1;
}
if(c2 < n && tree[c2] > tree[max]){
max = c2;
}
if(max != i){
swap(tree,max,i);
heapify(tree,n,max);//递归操作
}
}
void build_heap(int *tree,int n)
{
int last_node = n - 1;//表示最后一个节点
int parent_node = (last_node - 1) / 2;//表示最后一个节点的父节点
int i;
for(i = parent_node;i >= 0;i--){//循环heapify父节点，完成堆的构建
heapify(tree,n,i);
}
}
void heap_sort(int *tree,int n)
{
assert(tree != nullptr);
build_heap(tree,n);//调用数构建堆函数
int i = 0;
for(i = n - 1;i >= 0;i--){//循环对最后一个节点和根节点进行交换，并重构堆
swap(tree,i,0);
heapify(tree,i,0);
}
}
int main()
{
int tree[] = {4,10,3,5,1,2};
int n = 6;
heap_sort(tree,n);
for(int i = 0;i < n;i++){
printf("%d ",tree[i]);
}
return 0;
}对堆排序的总结：
其实我学习堆排序的时间只用了四十分钟不到就明白了基本原理并且通过代码实现了堆排序，但是需要从开始讲述堆排序却是一件不容易的事，我们得从数据结构的四种数据类型开始梳理，理解什么是完全二叉树并对堆这种数据类型有一个深刻的理解才能开始实现堆排序。
堆是计算机科学中一类特殊的数据结构的统称，通常是一个可以被看做一颗完全二叉树的数组对象。而堆排序正是利用堆这种数据结构所设计的一种排序算法。
建堆的时间复杂度：O（N）
堆排序的时间复杂度为O（N*LogN）
很荣幸观看并学习到了up主正月点灯笼的堆排序视频。