经典的要取一堆数组中最大的或者最小的前K个数据
方法1.遍历一遍，排序（升或者降序）然后找K个最大的
优点：好想
缺点：时间复杂度过高
方法2.N个树一次插入大堆，POP K次，每次都取堆顶数据，一共前K个
O（N+logN*k）
一次pop差不多是logN，但是其实只有最后一个才是logN
方法3.假设N特别大，内存中存不下差不多好几亿（基本数据用栈存，复杂数据用堆，栈少，堆多），他们就存在文件中
（1）先用前K个数建立小堆（一般都反着来，升序看小堆，降序找大堆）
（2）剩下N- K个数依次与小堆的堆顶比较，比小堆的堆顶大的，就要换堆顶，从而保留出最大的那十个数字，（如果是大堆，则会因为有一个最大的，而导致无法进入大堆里面），
（3）最后堆里有K个数，就是最大的那几个
void PrintTopK(int*a,int n,int k){ HP hp; HeapInit(&hp); //初始化小堆 for(int i=0;i<k;i++){ HeapPush(&hp,a[i]); //建立一个小堆，里面有K个数 } for(int i=k;i<n;++i){ if(a[i]>HeapTop(&hp)) hp.a[0]=a[i]; AdjustDown(hp.a,hp.size,0); } HeapPrint(&hp); HeapDestroy(&hp);}
1. int main(){ 2. int n=100000; 3. int *a=(int *)malloc(sizeof(int)*n); 4. for(int i=0;i<n;++i){ 5. a[i]=rand()%1000000;} 6. a[2]=1000003; 7. a[6]=1000006; 8. a[10]=1000032; 9. a[3]=1000001; 10. a[61]=1000026; 11. a[62]=1000046; 12. a[63]=1000056; 13. a[64]=1000066; //确保有十个数大于一百万的 14. a[65]=1000076; 15. a[66]=1000086; 16. PrintTopK(a, 100000, 10); 17. 18. 19. return 0; 20. } 21.
int main(){ int n=100000; int *a=(int *)malloc(sizeof(int)*n); for(int i=0;i<n;++i){ a[i]=rand()%1000000;} a[2]=1000003; a[6]=1000006; a[10]=1000032; a[3]=1000001; a[61]=1000026; a[62]=1000046; a[63]=1000056; a[64]=1000066; //确保有十个数大于一百万的 a[65]=1000076; a[66]=1000086; PrintTopK(a, 100000, 10); return 0; }
