数据结构考研分类复习真题 第五章 答案[44]

（）在n个正整数中选出k(k<<m）个最大的数应使用堆排序方法对深度为h的堆筛选算法中关键字的比较次数至多为（h）次建堆总共进行的关键字比较次数不超过n堆排序在最坏情况下的时间复杂度是O(nlogn）

int r[]; // r[]是整型数组

（）void sift(int r[]int kmtag)

//已知r[k+m]是堆本算法将r[km]调整成堆tag=建立大根堆tag=建立小根堆

{i=k;j=*i;x=r[k];

while (j<=m)

{if (tag==) //建立小根堆

{if (j<m && r[j]>r[j+]) j++;//沿关键字小的方向筛选

if(r[j]<x)) {r[i]=r[j];i=j;j=*i;}

else break;}

else //建立大根堆

{if (j<m && r[j]<r[j+]) j++;//沿关键字小的方向筛选

if(r[j]>x) {r[i]=r[j];i=j;j=*i;}

else break;}

}

r[i]=x;

}//sift

main(int argcchar *argv[])

//根据命令行中的输入从个数中选取n个最大数或n个最小数

{int m=ij;

n=augv[]; //从命令行输入的第二个参数是需要输出的数的个数

if(n>m){printf(参数错误\n);exit();}

for(i=;i<m;i++) scanf(%d&r[i]); //输入个大小不同的正整数

if (augv[]==a) //输出n个最大数要求建立大根堆

{for(i=m/;i>;i) sift(rim)

printf(%d个最大数依次为\nn);

for(i=m;i>mn+;i) //输出n个最大数

{printf(%dr[i]); j++; if((j+)%==) printf(\n);//一行打印个数

sift(ri); } //调堆

}

else //(augv[]==i) //输出n个最小数要求建立小根堆

{for(i=m/;i>;i) sift(rim)

printf(%d个最小数依次为\nn);

for(i=m;i>mn+;i) //输出n个最小数

{printf(%dr[i]); j++; if((j+)%==) printf(\n);//一行打印个数

sift(ri); } //调堆

}

}//main

[算法讨论]算法讨论了建堆并输出n（n小于等于m）个最大(小)数的情况由于要求输出n个最大数或最小数必须建立极大化堆和极小化堆注意输出时的for循环控制到变量i从m变化到mn+这是堆的性质决定的只有堆顶元素才是最大(小)的要避免使i从到n来输出n个最大(小)数的错误

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []