（）在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個最大(小)數的錯誤
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23026.html
