堆的应用！--求第k大数

求一个数列中的第k大的数，将前k个数建最小堆，后面若比堆顶元素还小，则舍去，否则将堆顶置换成该元素，然后维护堆，最后输出堆顶元素~~

若求第k小的数，则只需建最大堆即可。

#include <stdio.h>

int a[101]; int n; ?void down(int i) ?{ ???? int t,temp; ???? while(i*2<=n) ???? { ???????? if (a[i]>a[i*2]) ??????????? t=i*2; ???????? else ??????????? t=i; ???????? if ((i*2+1<=n)&&(a[t]>a[i*2+1])) ??????????? t=i*2+1; ???????? if (t!=i) ???????? { ???????????? temp=a[t]; ???????????? a[t]=a[i]; ???????????? a[i]=temp; ???????????? i=t; ???????? } ???????? else break; ??? } ?} ??? int main() ??? { ??????? int k,num,i; ??????? scanf("%d%d",&k,&n); ??????? num=n;//因为n是会变化的，所以要记录下来 ??????? for (i=1;i<=n;i++) ??????????? scanf("%d",&a[i]); ??????? for (i=k/2;i>=1;i--) ??????????? down(i);//把前k个元素建立成最小堆,堆顶就是现在的第k大元素 ??????? for (i=k+1;i<=n;i++) ??????????? if (a[i]>a[1]) ??????? { ??????????? a[1]=a[i];//把堆顶元素置换掉 ??????????? down(1); ??????? } ??????????? printf("%d ",a[1]); ??????????? printf("n"); ??????????? return 0; ??? }