尋找最大或最小的K個數

題目描述

：在好幾億個數據中找出最大或最小的K個數。

分析：這幾億的數據肯定不能一起加載到內存中去，更不能對這些數據直接進行排序，因此我們這里講用數據結構中的 堆 來解決這個問題。

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

步驟：

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

2. 從第101個數據開始，每讀取一個數據，就與堆頂的元素進行比較，如果該數據大于堆頂的數據，則將堆頂的數據替換為該數據，并對這個小堆進行調整。

3. 重復步驟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();
}