topK问题——N个数中取最大的K个数

topK问题

在海量数据中找出出现频率最高的前k个数，或者从海量数据中找出最大的前k个数，这类问题通常被称为topK问题。

N个数中取最大的K个数，用小根堆；N个数中取最小的K个数，用大根堆；时间复杂度O(NlogK)。

例题1：100万个数中，找到其中最大的100个数。(N个数中取最大的K个数)

思路：

(1) 定义两个数组，arr用于存储海量数据N，top用于存储小根堆K；

(2) 将海量数据的前K个元素先填满top堆;

(3) 调整top堆为最小堆结构;

(4) 通过遍历将新数据与堆顶元素（此时堆顶元素最小）比较，大于堆顶元素就入堆，并下调堆结构。

(5) 遍历结束，则堆中的元素即N个数中最大的前K个数。

代码如下：

#include<iostream>
#include<cassert>
#include<ctime>

using namespace std;

const int N = 100000;
const int K = 10;

void adjustDown(int *top, int i)
{
	int child = 2 * i + 1;
	int min = i;
	while (min < K/2)
	{
		if (child + 1 < K&&top[child] > top[child + 1])
			child++;
		if (child<K&&top[min]>top[child])
		{
			swap(top[min], top[child]);
			min = child;
			child = 2 * min + 1;
		}
		else
			break;
	}
}

void topK(int *arr, int *top)
{
	assert(arr != nullptr&&top != nullptr);
	for (int i = 0; i < K; i++)
	{
		top[i] = arr[i];
	}
	for (int i = K / 2 - 1; i >= 0; i--)
	{
		adjustDown(top, i);
	}
	for (int i = K; i < N; i++)
	{
		if (arr[i]>top[0])
		{
			top[0] = arr[i];
			adjustDown(top, 0);
		}
	}
	for (int i = 0; i < K; i++)
		cout << top[i] << " ";
	cout << endl;
}

int main()
{
	int arr[N];
	int top[K];
	srand((unsigned)time(0));//随机种子
	for (size_t idx = 0; idx < N; ++idx)
	{
		arr[idx] = rand() % 10000;
	}
	topK(arr, top);
	return 0;
}