<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，如需转载请自行联系原作者