OK.
1,[n/2]-1 nodes;
2,Others are not nodes;
3,Time < =2nlog2(n)
//Get the max heap
void sift(int *a,int n)
{
int i,j,k;
for(i=(n/2-1);i>=0;i--)
{
k=i;
j=2*k+1;
int temp=*(a+k);
int flag=0;
while(flag==0 && j<n)
{
if(*(a+j)<*(a+j+1))
j++;
if(temp<*(a+j))
{
*(a+k)=*(a+j);
k=j;
}
else
flag=1;
*(a+k)=temp;
}
}
}
void heapsort(int *a,int n,int out[])
{
int k;
int i,j;
j=0;
int temp;
sift(a,n);
for(k=0;k<n-j;k++)
printf("%d ",a[k]);
printf("\n");
for(i=n-1;i>1;i--)
{
out[j]=*a;
j++;
//swap
temp=*a;
*a=*(a+i);
*(a+i)=temp;
sift(a,i-1);
}
out[j]=a[0]>a[1] ? a[0]:a[1];
out[j+1]=a[0]<a[1] ? a[0]:a[1];
}
中国源码网: 中国人的开放源代码社区
网络安全 博客 下载 手机编程
论坛 English 编程手册
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
