<pre name="code" class="cpp"><pre name="code" class="cpp">/**堆排序*/
/**顺序表存储*/
#include<cstdio>
#include<algorithm>
#define LT(a,b) ((a)<(b))
using namespace std;
int a[]={9,5,2,1,3,4,6,8,9,10};
int n=5;
void f(int s,int m){
/**使a[s...m]成为一个大顶堆*/
int c = a[s];
for(int j=2*s; j<=m; j*=2){
/**沿key较大的孩子节点向下筛选*/
if(j < m && LT(a[j],a[j+1])) ++j;
/**j为key较大记录的下标*/
if(!LT(c,a[j])) break;
/**rc应插入在位置s上*/
a[s]=a[j];
s=j;
}
a[s]=c;
}
void Hs(){
/**把a[1...n]建成大顶堆*/
for(int i=n/2; i>0; --i)
f(i,n);
for(int i=n;i>1;--i){
swap(a[1],a[i]);
/**把堆顶最大的和最后一个交换*/
f(1,i-1);
/**将a[1,i-1]又一次调整为大顶堆*/
}
}
int main()
{
Hs();
for(int i=1;i<=5;i++) printf("%d ",a[i]);
return 0;
}
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5395863.html，如需转载请自行联系原作者