TopK问题与堆排序

TopK问题：

定义：

应用场景：

搜索引擎：

推荐系统：

数据分析：

数据挖掘：

TopK问题初阶：（数据量较小情况）

TopK问题进阶：（数据量较大情况）

堆排序：

堆排序排升序：

建小堆：

建大堆：

堆排序排降序：

建大堆：

建小堆：

TopK问题：

定义：

TopK问题即求数据集合中前K个最大的元素或者最小的元素。

应用场景：

搜索引擎：

在搜索引擎中，TopK问题可以用于返回用户查询的前K个最相关的搜索结果

数据分析：

在大数据分析中，TopK问题可用于查找最频繁出现的元素或最高价值的数据点。

数据挖掘：

在聚类和分类问题中，可以使用TopK问题来选择具有最高重要性的特征或数据点。

TopK问题初阶：（数据量较小情况）

假设从M中个数据选出前N个大的（小的）数据，需要先对M个数据建堆，对于堆结构使用取堆顶数据算法（HeapTop）再将最后一个元素移到第一个元素的位置，再使用向上调整（Adjustup）/向下调整算法（Adjustdown），不断执行这个过程N次，便可得到前N个大的（小的）数据。

void AdjustUp(HeapDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void Adjustdown(HeapDataType* a, int n, int parent)
{
	size_t child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

HeapDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

TopK问题进阶：（数据量较大情况）

TopK问题初阶的解决方法仅适用于M小的情况，如果M的数据量较大，则TopK问题初阶算法不再试用。假设M为10亿，对于M数据量建堆需要消耗约40个G的内存，此时内存不够用，可以使用硬盘存储，但还有更加简单的方法。

可以先对前N个数据建堆，若想取出前N个大的数据，则应该建立小堆，将后续的（M-N）个数据不断与堆顶数据进行比较，如果数据大于堆顶元素，则将数据与堆顶元素进行交换，并使用向下调整算法使堆保持小堆结构，最后小堆内剩下的N个数据就是M个数据内想取出的前N个数据。

若想取出前N个小的数据，则应该建立大堆，将后续的（M-N）个数据不断与堆顶数据进行比较，如果数据小于堆顶元素，则将数据与堆顶元素进行交换，并使用向下调整算法使堆保持大堆结构，最后大堆内剩下的N个数据就是M个数据内想取出的前N个数据。

时间复杂度：N+（M-N）logK—>N

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (int i = 0; i < n; ++i)
	{
		int x = (rand()+i) % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

//前k个数据为例
void topk()
{
	printf("请输入k：>");
	int k = 0;
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	int val = 0;
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}

	// 建k个数据的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}

	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		// 读取剩余数据，比堆顶的值大，就替换他进堆
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}

	fclose(fout);

}

堆排序：

堆排序排升序：

建小堆：

堆顶元素即为整个数据内最小元素，但后部元素只有孩子大于父亲的关系，没有孩子与孩子之间的关系，所以如果使用建小堆实现堆排序升序则需对于剩下的元素再进行建堆。

时间复杂度为N*logN

void HeapSort(int* a, int n)
{
	// a数组直接建堆 O(N)
	for (int i = (n-1-1)/2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}