题目描述
：在好几亿个数据中找出最大或最小的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();
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
