重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
/***************************** 复杂度:
***************************/ #include#include #include #include #include using namespace std; #define N 1000 #define K 100 void AdjustDown(int *a, size_t root, size_t size) { //向下调整小堆 size_t parent = root; size_t child = parent * 2 + 1; while (child < size) { if (child + 1 < size && a[child] > a[child + 1]) { ++child; } if (a[parent] > a[child]) { swap(a[parent], a[child]); parent = child; child = parent * 2 + 1; } else//注意不满足交换条件时跳出本次循环 { break; } } } void GetTopk(const vector & Vnumber, int n, int k)//N个数中找最大的前k个数--小堆实现 { assert(n>k); int *TopkArray = new int[k];//通过前k个元素建立含有k个元素的堆 for (size_t i = 0; i < k; i++) { TopkArray[i] = Vnumber[i]; } for (int i = (k - 2) / 2; i >= 0; --i)//建小堆 { AdjustDown(TopkArray, i, k); } //从第k个元素开始到第n个元素分别与堆顶元素进行比较,较大数据入堆顶,再对整个堆进行下调,使堆顶存放最小元素(小堆) for (size_t i = k; i < n; ++i) { if (Vnumber[i] > TopkArray[0]) { TopkArray[0] = Vnumber[i]; AdjustDown(TopkArray, 0, k); } } size_t count = 0; for (size_t i = 0; i < k; ++i)//打印k个最大数据,即堆中所有元素 { cout << TopkArray[i] << " "; ++count; if (count % 10 == 0) { cout << endl; } } cout << endl; delete[] TopkArray;//注意释放TopkArray所占的内存 TopkArray = NULL; } void CreateVnumber(vector & Vnumber)//创建N个数 { srand((unsigned int)time(NULL)); //srand(time(0)); Vnumber.reserve(N); for (size_t i = 0; i Vnumber; CreateVnumber(Vnumber); GetTopk(Vnumber, N, K); //int length = Vnumber.size(); //for(int i=0;i
文章标题:小代码寻找K个最大的数
文章分享:http://cqcxhl.com/article/jiosio.html