您好,登錄后才能下訂單哦!
題目描述
:在好幾億個(gè)數(shù)據(jù)中找出最大或最小的K個(gè)數(shù)。
分析:這幾億的數(shù)據(jù)肯定不能一起加載到內(nèi)存中去,更不能對這些數(shù)據(jù)直接進(jìn)行排序,因此我們這里講用數(shù)據(jù)結(jié)構(gòu)中的 堆 來解決這個(gè)問題。
假定這里要從100000個(gè)數(shù)據(jù)中找出最大的100個(gè)數(shù)據(jù),這樣是為了描述方便,我們這里直接用一個(gè)數(shù)組來存儲這個(gè)100000個(gè)數(shù)據(jù),如果數(shù)據(jù)多達(dá)好幾億,則只需將這些數(shù)據(jù)放入文件中進(jìn)行讀寫即可,這里為了描述問題方便就這樣假定。
步驟:
取出這些數(shù)據(jù)中前100個(gè)數(shù)據(jù),然后用這些數(shù)據(jù)建立一個(gè)小堆;
從第101個(gè)數(shù)據(jù)開始,每讀取一個(gè)數(shù)據(jù),就與堆頂?shù)脑剡M(jìn)行比較,如果該數(shù)據(jù)大于堆頂?shù)臄?shù)據(jù),則將堆頂?shù)臄?shù)據(jù)替換為該數(shù)據(jù),并對這個(gè)小堆進(jìn)行調(diào)整。
重復(fù)步驟2,等到所有數(shù)據(jù)都取完后,則留下的這個(gè)堆中的100個(gè)元素,就是我們要得到的最大的100個(gè)數(shù)。
代碼如下:
#pragma once #include<iostream> #include<time.h> using namespace std; #define N 100000 //N個(gè)數(shù)據(jù) #define K 100 //最大或最小數(shù)據(jù)的個(gè)數(shù) //仿函數(shù),可以選最大的K個(gè)數(shù),也可以選最小的K個(gè)數(shù) 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> //默認(rèn)建小堆 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個(gè)數(shù) { 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; //計(jì)算左孩子 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; //產(chǎn)生N個(gè)10000以內(nèi)的隨機(jī)數(shù) } Heap<int, Less<int>> get_K(randNum, K); //小堆 選最大的K個(gè)數(shù) 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; //產(chǎn)生N個(gè)10000以內(nèi)的隨機(jī)數(shù) } Heap<int, Greater<int>> get_K(randNum, K); //大堆 選最小的K個(gè)數(shù) get_K.CreatHeap(); get_K.GetK(randNum, N); get_K.Print(); }
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。