您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
/***************************** 复杂度:
***************************/ #include<iostream> #include<assert.h> #include<vector> #include<stdlib.h> #include<time.h> 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<int>& 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<int>& Vnumber)//创建N个数 { srand((unsigned int)time(NULL)); //srand(time(0)); Vnumber.reserve(N); for (size_t i = 0; i<N; i++) { Vnumber.push_back(rand() % 1000);//产生N个随机值 } for (size_t i = K; i < N; ++i) { Vnumber[i] *= 100; } } int main() { vector<int> Vnumber; CreateVnumber(Vnumber); GetTopk(Vnumber, N, K); //int length = Vnumber.size(); //for(int i=0;i<length;i++) //{ // cout<<Vnumber[i]<<" "; // } return 0; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。