您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
题目描述
:在好几亿个数据中找出最大或最小的K个数。
分析:这几亿的数据肯定不能一起加载到内存中去,更不能对这些数据直接进行排序,因此我们这里讲用数据结构中的 堆 来解决这个问题。
假定这里要从100000个数据中找出最大的100个数据,这样是为了描述方便,我们这里直接用一个数组来存储这个100000个数据,如果数据多达好几亿,则只需将这些数据放入文件中进行读写即可,这里为了描述问题方便就这样假定。
步骤:
取出这些数据中前100个数据,然后用这些数据建立一个小堆;
从第101个数据开始,每读取一个数据,就与堆顶的元素进行比较,如果该数据大于堆顶的数据,则将堆顶的数据替换为该数据,并对这个小堆进行调整。
重复步骤2,等到所有数据都取完后,则留下的这个堆中的100个元素,就是我们要得到的最大的100个数。
代码如下:
#pragma once #include<iostream> #include<time.h> using namespace std; #define N 100000 //N个数据 #define K 100 //最大或最小数据的个数 //仿函数,可以选最大的K个数,也可以选最小的K个数 template<class T> struct Less { bool operator()(const T& num1, const T& num2) { return num1 < num2; } }; template<class T> struct Greater { bool operator()(const T& num1, const T& num2) { return num1 > num2; } }; template<class T, class com = Less> //默认建小堆 class Heap { public: Heap(const T* a, size_t size) :MaxOrMinK(new T[size]) , _size(size) { for (size_t i = 0; i < _size; ++i) { MaxOrMinK[i] = a[i]; } } ~Heap() { if (_size > 0) delete[] MaxOrMinK; } void CreatHeap() // 建堆,(小/大) { for (int i = (_size - 2) / 2; i >= 0; --i) { AdjustDown(MaxOrMinK, _size, i); } } void GetK(const T* array, size_t size) //从array中选出最大(或最小)的K个数 { for (int i = K; i < size; ++i) { if (com()(MaxOrMinK[0], array[i])) { MaxOrMinK[0] = array[i]; AdjustDown(MaxOrMinK, _size, 0); } } } void Print() { if (_size > 0) { for (size_t i = 0; i < _size; ++i) { cout << MaxOrMinK[i] << endl; } } } protected: void AdjustDown(T*& a, size_t size, size_t root) { size_t child = root * 2 + 1; //计算左孩子 while (child < size) { if (child + 1 < size && com()(a[child + 1], a[child])) { ++child; } if (com()(a[child], a[root])) { std::swap(a[root], a[child]); root = child; child = root * 2 + 1; } else { break; } } } private: T* MaxOrMinK; size_t _size; }; void Test1() { int randNum[N]; srand(time(NULL)); for (int i = 0; i < N; ++i) { int tmp = rand() % 10000; randNum[i] = tmp; //产生N个10000以内的随机数 } Heap<int, Less<int>> get_K(randNum, K); //小堆 选最大的K个数 get_K.CreatHeap(); get_K.GetK(randNum, N); get_K.Print(); } void Test2() { int randNum[N]; srand(time(NULL)); for (int i = 0; i < N; ++i) { int tmp = rand() % 10000; randNum[i] = tmp; //产生N个10000以内的随机数 } Heap<int, Greater<int>> get_K(randNum, K); //大堆 选最小的K个数 get_K.CreatHeap(); get_K.GetK(randNum, N); get_K.Print(); }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。