面试的时候总是不免在数据结构方面会遇到堆排序的问题，相信很多人都只是知道冒泡排序，插入排序这种简单的，更甚者还知道合并排序以及快速排序
至少对于我自己来说是觉得堆排序很不常见的~平时写代码也就是一个sort函数，教科书里也不怎么见到过，但真正问起里面的细节过程了怎么办- -，果然还是得老老实实学习啊，了解merge sort 以及 quick sort的同学相信会觉得这个heap sort很简单的~

n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：

(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），当然，这是小根堆，大根堆则换成>=号。//k(i）相当于二叉树的非叶子结点，K(2i）则是左子节点，k(2i+1）是右子节点

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：堆中任意一个节点上的值都不大于(或者不小于)其叶子节点对应的值

定义

对于一个1....n的序列，我们可以将其看成是一棵完全二叉树，那么当前点的位置是o

那么它的左儿子就是o<<1(o*2) , 右儿子就是o<<1|1(o*2+1)

也就是简单来说所有的非叶子节点都满足 val[o]<=val[o<<1] && val[o]<=val[o<<1|1]那么这就是一个最小堆

同理所有的非叶子节点都满足 val[o]>=val[o<<1] && val[o]>=val[o<<1|1]那么这就是一个最大堆

堆排序思路

我们的目标说白了就是排序，而这里只是利用堆的特性进行排序比如我们希望得到的是由大到小的排序，那么我们必然构建的是最大堆，这样每次堆顶的元素必然是最大的那个元素，我们只要不断地把堆顶的元素取出来就得到了一个由大到小的正确排序了

那么也就是说我们面临的问题就是

1.如何构建一个初始的堆

2.如何在获取当前最大的堆顶元素之后对这个堆进行更新以便自己获得下一个最大的元素(也就是新的堆顶)

构建初始堆

在这里我以构建最大堆来举例说明

比如当前给了你要排序的数组是a[]= {16,7,3,20,17,8}

我们先只要把他们一个个放到堆的节点中即可得到:

这里非叶子节点就是16,7,3
我们只要判断非叶子节点是否符合最大堆的特性即可，因为叶子节点就自己本身没必要在比较了

从后往前：

1.3会与8交换 

2.20与7交换

3.16与20交换

4.16交换到a[3]的位置上，发现此时17>16，那么16再与17交换

从第四步可以看出，每次如果换到下一层的元素违反了堆的性质，说明是要不断递归往下更新的，这里交换的代码的话就需要做到递归了

对于从前往后更新的点的话，我们可以很容易得知的是其实应该最后一个非叶子节点是a[n/2]

这里稍微简单的证明一下：

当然不清楚的话直接从n开始也可以，判断一下他有没有叶子节点就行

void build_heap(int n)

{

    int len = n/2;

    for(int o=len ; o>0 ; o--){

        update(o , n);

    }

}

最后就应该得到的是

堆的更新

我们每次取得最顶点的元素作为当前a[1~i]堆的最大值，然后把堆顶元素和最后一个元素换一个位置，表示不再需要这个元素参与排序了，因为已经取到过了

那么就从之前的a[1~i]变成了a[1~(i-1)]堆的排序更新了。

很容易就可以知道只有从最顶端开始往下某一个方向上的值需要更新，因为每次往下方交换只会找到一个方向，那么更新完成最多更新了log（n）次，也就是堆的深度

1.最开始交换位置之后，最大的20和最后一个3交换了

2.3的左儿子17最大，3和17交换后，又发现3此时的右儿子16最大，那么3和16交换到达了最底层不再更新得到：

那么后续就是：

其实讲了这么多根本上只要用到开始给的那个update函数即可，只是需要每次把总的节点个数减一

将两幅截图的代码合到一起就可以算出一个由大到小排列的序列了

时间空间复杂度分析

身为一个程序员连复杂度都不考虑那真是太蠢了- -

这里在构建初始的堆我们因为是从后往前将一个个非叶子节点更新的，所以复杂度是O(n)

而之后每次取到堆顶之后更新因为是从上至下一个方向上的更新，所以每次更新都是O(logn)的，那么总共取到n次，那就是nlog(n)的复杂度

那么整个程序自然就是O(nlog(n)+n)的了，是很不错的一种排序方式了~~