100萬個數(shù)中找出最大的前K個數(shù)

   拿到這個題目我想到了很多方法，但是在我想到的方法中，要把在100萬個數(shù)中找到前k個數(shù)，都不適用。最后通過我的不斷研究，我想到了我認(rèn)為最簡單的方法，就是利用堆來做這道題目。

   下面我分析一下我用堆排序的思路：

     1.我先建一個大小為k的堆。

     2.把100萬中前k個數(shù)放到這個堆中。

     3.把這個堆調(diào)成小堆。

     4.把100萬個從k到100萬之間的數(shù)字拿出來和堆的根結(jié)點作比較。

     5.如果根結(jié)點小于這之間的某一個數(shù)，就把這個數(shù)拿給根結(jié)點，然后繼續(xù)調(diào)成小堆。否則繼續(xù)找

     6.直到找完這100萬個數(shù)，堆中放的就是最大的前k個數(shù)。

代碼如下：

//下調(diào)
void _AdjustDown(int *arr, int parent, int size)
{
	int child = 2 * parent + 1;
	while (child<size)
	{
		//child + 1 < size保證是最后一個節(jié)點
		if (child + 1 < size&&arr[child] > arr[child + 1])
		{
			child++;//保證是孩子結(jié)點最大的一個節(jié)點
		}
		//交換
		if (arr[child] < arr[parent])
		{
			swap(arr[child], arr[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
int* Find(int *arr, int k,int N)
{
	assert(arr);
	assert(k > 0);
	int *str = new int[k];
	//把前k個元素放在堆中
	for (int i = 0; i < k; i++)
	{
		str[i] = arr[i];
	}
	//調(diào)成最小堆
	for (int j = (k - 2) / 2; j >= 0; j--)
	{
		_AdjustDown(str, j, k);
	}
	//然后k到N的所有數(shù)與堆中的根結(jié)點相比較
	for (int n = k; n < N; n++)
	{
		if (str[0] < arr[n])//如果根結(jié)點小于堆中k到N中的某一元素
		{
			str[0] = arr[n];//把這個元素賦值給根結(jié)點
			_AdjustDown(str, 0, k);//再一次調(diào)成最小堆
		}
	}
	return str;
	delete[]str;
}

  希望這個對你們有幫助。期待你們的回復(fù)，有什么不對的地方可以指出來啊。