(from wikipedia)
构建步骤:
- 建成一个大顶堆
- 第一个元素依次和最后一个元素交换，由于交换后新的堆顶元素可能违反大根堆的性质，因此需要对当前无序区(1，2，...，n-1）调整为新堆
- 不断重复此过程直到有序区的元素个数为n-1
- 排序完成
下面举例说明：
给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序。
首先根据该数组元素构建一个完全二叉树，得到
然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：
第一步: 初始化大顶堆(从最后一个有子节点开始往上调整最大堆)
20和16交换后导致16不满足堆的性质，因此需重新调整
这样就得到了初始堆。
第二步: 堆顶元素R[1]与最后一个元素R[n]交换，交换后堆长度减一
即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。
第三步: 重新调整堆。此时3位于堆顶不满堆的性质，则需调整继续调整(从顶点开始往下调整)
重复上面的步骤:
不管是初始大顶堆的从下往上调整，还是堆顶堆尾元素交换，每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换，交换之后都可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整。
（出自http://www.cnblogs.com/0zcl by前程明亮)
现在
开始
代码：
int main(){
cin>>n;
for( int i=; i<=n; i++){
cin>>a[i];
}
heap_sort();
for( int i=; i<=n; i++){
printf("%d ",a[i]);
}
return ;
}
main函数
（主函数不多说
void heap_sort(){
for( int i=n; i>=; i--){
update(i,n);
}
for( int i=n-; i>=; i--){
swap(a[i+],a[]);
update(,i);
}
}
heap_sort
首先就是建立大根堆：
for( int i=n; i>=; i--)update(i,n);
关于这个update函数是这样的：
对输入的两个数组的地址 i 和 n
- 如果 i 的左儿子比 n 还大，那么退出
- 如果 i 的右儿子比左儿子大，那么把地址指向右儿子，否则地址是指向i 的左儿子的
- 如果 t 指向的这个数组的值大于 n 指向的值，那么交换这两个值
- 继续递归地update t 和 n
然后就是heap_sort的内涵：
for( int i=n-; i>=; i--){
swap(a[i+],a[]);
update(,i);
}
大致就是这样。
完整代码如下：
#include <cstdio>
#include <iostream>
using namespace std; int n;
int a[]; #define lson(x) (x*2) void update(int x, int m){
int t=lson(x);
if(t>m)return ;
if(t<m && a[t+]>a[t])t++;
if(a[t]>a[x])swap(a[x],a[t]);
update(t,m);
} void heap_sort(){
for( int i=n; i>=; i--){
update(i,n);
}
for( int i=n-; i>=; i--){
swap(a[i+],a[]);
update(,i);
}
} int main(){ cin>>n;
for( int i=; i<=n; i++){
cin>>a[i];
} heap_sort(); for( int i=; i<=n; i++){
printf("%d ",a[i]);
} return ;
}