最小的k個數

最小的k個數

輸入n個數，找出其中的最小的k個數。

思路：設置一個長度為k的大頂堆，比較第k+1,k+2...n與堆頂元素的大小，如果比堆頂元素小，則交換，並重新維持大頂堆的性質。

參考代碼：

root@gt:/home/git/Code# ./a.out 4312root@gt:/home/git/Code# cat topk.c #include <stdio.h>void exchange(int* pa,int* pb){ int temp = *pa; *pa = *pb; *pb = temp;}void max_heap(int* parr,int heap_size,int index){ int left = 2 * index; int right = 2 * index + 1; int max_index; if(left < heap_size && parr[left] > parr[index]) max_index = left; else max_index = index; if(right < heap_size && parr[right] > parr[max_index]) max_index = right; if(max_index != index) { exchange(&parr[index],&parr[max_index]); max_heap(parr,heap_size,max_index); }}void build_max_heap(int* parr,int len){ for(int i = (len - 2)/2;i >= 0;--i) max_heap(parr,len,i);}int main(){ int parr[] = {4,5,1,6,2,7,3,8}; build_max_heap(parr,4); for(int i = 4;i < sizeof(&parr);++i) { if(parr[i] < parr[0]) { exchange(&parr[i],&parr[0]); max_heap(parr,4,0); } } for(int i = 0;i < 4;++i) printf("%d
",parr[i]); return 0;}

推薦閱讀：