題目描述

網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)介紹好的網(wǎng)站是理念、設(shè)計和技術(shù)的結(jié)合。創(chuàng)新互聯(lián)建站擁有的網(wǎng)站設(shè)計理念、多方位的設(shè)計風(fēng)格、經(jīng)驗豐富的設(shè)計團隊。提供PC端+手機端網(wǎng)站建設(shè)，用營銷思維進行網(wǎng)站設(shè)計、采用先進技術(shù)開源代碼、注重用戶體驗與SEO基礎(chǔ)，將技術(shù)與創(chuàng)意整合到網(wǎng)站之中，以契合客戶的方式做到創(chuàng)意性的視覺化效果。

：在好幾億個數(shù)據(jù)中找出大或最小的K個數(shù)。

分析：這幾億的數(shù)據(jù)肯定不能一起加載到內(nèi)存中去，更不能對這些數(shù)據(jù)直接進行排序，因此我們這里講用數(shù)據(jù)結(jié)構(gòu)中的 堆 來解決這個問題。

假定這里要從100000個數(shù)據(jù)中找出大的100個數(shù)據(jù)，這樣是為了描述方便，我們這里直接用一個數(shù)組來存儲這個100000個數(shù)據(jù)，如果數(shù)據(jù)多達好幾億，則只需將這些數(shù)據(jù)放入文件中進行讀寫即可，這里為了描述問題方便就這樣假定。

步驟：

1. 取出這些數(shù)據(jù)中前100個數(shù)據(jù)，然后用這些數(shù)據(jù)建立一個小堆；

2. 從第101個數(shù)據(jù)開始，每讀取一個數(shù)據(jù)，就與堆頂?shù)脑剡M行比較，如果該數(shù)據(jù)大于堆頂?shù)臄?shù)據(jù)，則將堆頂?shù)臄?shù)據(jù)替換為該數(shù)據(jù)，并對這個小堆進行調(diào)整。

3. 重復(fù)步驟2，等到所有數(shù)據(jù)都取完后，則留下的這個堆中的100個元素，就是我們要得到的大的100個數(shù)。

代碼如下：

#pragma once
#include
#include
using namespace std;

#define N 100000  //N個數(shù)據(jù)
#define K 100     //大或最小數(shù)據(jù)的個數(shù)


//仿函數(shù)，可以選大的K個數(shù)，也可以選最小的K個數(shù)
template
struct Less
{
	bool operator()(const T& num1, const T& num2)
	{
		return num1 < num2;
	}
};

template
struct Greater
{
	bool operator()(const T& num1, const T& num2)
	{
		return num1 > num2;
	}
};


template  //默認建小堆
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個數(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;  //計算左孩子

		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個10000以內(nèi)的隨機數(shù)
	}

	Heap> get_K(randNum, K);  //小堆 選大的K個數(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個10000以內(nèi)的隨機數(shù)
	}

	Heap> get_K(randNum, K);  //大堆 選最小的K個數(shù)
	get_K.CreatHeap();
	get_K.GetK(randNum, N);
	get_K.Print();
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

新聞標(biāo)題：尋找最大或最小的K個數(shù)-創(chuàng)新互聯(lián)
網(wǎng)頁URL：http://weahome.cn/article/dpccdh.html