【数据结构与算法】利用堆结构高效解决TopK问题

void Swap(HPDataType* a, HPDataType* b)//交换函数
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}
void Adjustdown(HPDataType* a, int parent, int n)//向下调整算法
{
	assert(a);
	int 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;
	}
}

#if 1
//TOPK问题
void CreateNDate()// 造数据
{
	int n = 1000;
	srand(time(NULL));
	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() % 1000000;//写入百万以内的随机数
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
	fin = NULL;
}

void PrintTopK(int k)//求最大的k个元素
{
	int* arr = (int*)malloc(sizeof(int) * k);//动态申请数组
	const char* file = "data.txt";
	FILE* fin = fopen(file, "r");//打开文件
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < k; i++)//读入k个数据
	{
		fscanf(fin, "%d", &arr[i]);
	}
	for (int i = (k - 2) / 2; i >= 0; i--)//向下调整建堆
	{
		Adjustdown(arr, i, k);
	}

	int x = 0;
	while (fscanf(fin, "%d", &x) != EOF)//从文件读取数据
	{
		if (x > arr[0])//每次与堆顶比对
		{
			arr[0] = x;		//如果比堆顶数据大，覆盖堆顶数据
			Adjustdown(arr, 0, k);	//向下调整恢复堆
		}
	}
	printf("前k个元素：");
	for (int i = 0; i < k; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
#endif
int main()
{
	//test1();
	//CreateNDate();
	PrintTopK(10);
	return 0;
}