堆排序的平均时间复杂度均为O(nlogn)，也是所有排序算法里极其重要的一种。堆排序的实现可以节省空间，但免不了会牺牲稳定和时间。我在这做一个详细的堆排序实现的过程演示和c实现的完整代码。
堆(Heap)
堆就是用数组实现的二叉树。堆根据“堆属性”来排序，“堆属性”决定了树中结点的位置。
####特点：
堆分为两种：最大堆和最小堆，两者的差别在于节点的排序方式。
1.最大堆：父结点的元素总是大于或等于任何一个子节点的元素，即最大堆总是将其中的最大值存放在树的根节点。
2.最小堆：父结点的元素总是小于或等于任何一个子节点的元素。最小堆根节点中的元素总是树中的最小值。
而今天我们所举的所有例子均按照最大堆进行，即满足：
1.完全二叉树（complete binary tree）
2.父结点要大于子结点（parents > children）
堆化（Heapify)
从上向下不断将两个子结点与父结点比较，最大堆将较大的子结点与父结点交换（最小堆是将较小的子结点与父结点交换），这个过程就是堆化。
堆排序（Heap Sort)
对于堆排序来说的话，我们希望看到的是，先把一颗二叉树实现堆化，然后进行元素排序的一个过程。
堆的演示
比如我们现在有一颗树，如下图所示。
可能画的比较粗糙2333不是很圆，算了无所谓了。
我们知道最大堆的特点就是它必须是一颗完全二叉树，并且父结点一定比它的子结点大。
首先我们发现它确实是一颗完全二叉树，然后看下图红色框出来的地方，父结点10是比它的子结点8和2大的，当然了8和2的位置可以随便调换，whaterver
然后我们发现对于其他子树它也满足这个特点。所以我们就认为这颗树符合我的堆的特点，所以这就是一个堆。
堆化的演示
我们来看具体堆化的一个演示。注意哦，下面这个过程先是展示一个堆化的过程，还没有到堆排序的过程。
假设我们现在有一个如下图所示的完全二叉树。
我们发现，如下图红色框出来的地方，这棵树的底层已经是一个稳定的堆了
唯一不一样的就是最大的那一个是4，我们现在希望把这棵树变成一个堆，把它变成堆的过程就是堆化。
堆化就是我们从一个结点出发，我们它的左孩子和右孩子选一个最大的出来，和它的父结点做交换就可以了。
我们现在要做的就是把下面红色框出来的部分，实现一个堆化。
我们发现10是最大的，所以我们让10和4交换，变成下图。
然后我们发现，此时对于底下父结点为4的子树（如下图红色框出来的部分）就不满足堆了，那么我们继续做一个堆化。
我们继续取最大的5，和它的父结点4交换，此时我们发现父结点比子结点大，满足堆的条件了。
至此，我们发现这棵树已经全部满足堆的条件了（大顶堆），那么整个这个过程，就是堆化。知道了怎么堆化，下面堆排序就变得异常简单了。
堆排序前的准备
如果我们给刚刚那棵树都数组下标一样标上号，按0，1，2，3这样从父结点开始按照从左到右标号，这一部分后面敲代码的时候会用到。
我们是可以总结出对于每颗子树的父结点，我们把父结点写成parent,它的左孩子写成c1,右孩子写成c2，如下图所示。
都满足
####公式
parent=(i-1)/2;
c1=2i+1;
c2=2i+2;
这里的i就是刚刚我们标的号，即数组下标。要注意的是，计算之后不是整数要向下取整。
堆排序的演示
堆化完了我们就要堆排序了，是的，现在才是我们在这主要要干的事情
首先，我们要将堆顶和这棵树最后一个元素交换，也就是在刚这棵树里，我们1交换10和2
然后10跑到了最后面，因为我们已经完成了堆化，所以此时在交换了堆顶和最后一个元素后，最后那个数字一定是最大的数字，即10。
然后我们把10摘出去，变成下图。
我们发现现在又不满足堆了，怎么办，按前面的方法堆化，堆化以后变成下图。
然后我们继续交换堆顶和最后一个元素，这儿是交换5和1，然后5就变为了最后一个元素，摘出5.
那么5就是第二大的数字。之后的过程亦是如此，直到最后一个元素被摘出，我们也就完成了堆排序。
最终的结果就是1，2，3，4，5，10；
堆排序结束。
代码部分
####代码
#include <stdio.h>
void swap(int arr[],int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
void heapify(int tree[],int n,int i)//n代表这棵树里有多少结点，i表示对哪个结点做heapify
{
if(i>=n)
{
return;
}
int c1=2*i+1;
int c2=2*i+2;
int max=i;
if(c1<n&&tree[c1]>tree[i]) //最小堆的话把这和下面的大于改小于就好了
{
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;i>=0;i--) //从底层不断往上
heapify(tree,n,i);
}
void heap_sort(int tree[],int n)
{
build_heap(tree,n);
int i;
for(i=n-1;i>=0;i--)
{
swap(tree,i,0);
heapify(tree,i,0);//最后一个数因为要拎出来，i表示的是当前的结点个数
}
}
int main()
{
int tree[]={4,10,3,5,1,2};
int n=6;
build_heap(tree,n);
heap_sort(tree,n);
for(int i=0;i<n;i++)
{
pritnf("%d",tree[i]);
}
return 0;
}
