一、思路

1.先取所有数据中的前k个元素，将其构成小堆，此时堆顶元素是k个元素中最小的那个数据

2. 然后，就接着读取数据，如果读取到的数据大于堆顶元素，让其取代堆顶元素的位置，让其进入堆中，并调用向下调整函数，让当前堆中k个数据中，最小的数据来到堆顶位置，继续重复执行，直至读取完所有数据

3.这样就可以完成找到所有数据中的最大的前k个数据了（堆中的k个数据就是要找到的）

二、代码

1. 造数据

在文件中随机生成10万个数据

//1. 造数据 在文件中随机生成10万个数据
void CreateNDate()
{
	int n = 100000;
	srand((unsigned)time(NULL));//生成随机数种子
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");//打开文件，写数据
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000+i;//产生的随机数都比100万小
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);  //关闭文件
}

2.读数据

 

void PrintTopK(int k)
{
	int* p = (int*)malloc(sizeof(int) * k);//申请k个空间用来构建堆，存储数据
	FILE* fin = fopen("data.txt", "r");  //打开文件,读数据
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	int i;
	//先读取前k个数据，构建一个小堆。之后继续读取数据，
	// 如果比堆顶元素大，就让其取代堆顶元素，并调整堆，使得最小的元素在堆顶位置
	for (i = 0; i < k; i++)//先读取k个数据存放在数组中，构建一个小堆
	{
		fscanf(fin, "%d", &p[i]);
		AdjustUp(p, i);//边插入，边建立一个小堆
	}
	//接着读取剩下的数据
	int num;
	while (fscanf(fin, "%d", &num) > 0)
	{
		if (num > p[0])//如果数据大于堆顶元素，让其进入堆中，调整堆
		{
			p[0] = num;
			AdjustDown(p, k, 0);//调整堆
		}
	}
	//打印结果:最大的k个数据就在堆中
	for (i = 0; i < k; i++)
		printf("%d ", p[i]);
	fclose(fin);//关闭文件
}

 3.测试

int main()
{
	//CreateNDate();//创造数据
	int k = 0;
	printf("请输入k的值:>");
	scanf("%d", &k);
	printf("最大的前%d个数据是:>",k);
	PrintTopK(k);
	return 0;
}

 

 为了检验出算法的正确性，在存放数据的文件中，我们随机手动修改数据，让11个数据大于100万

2222222 3333333 4444444 7777777 5555555 10101010 9999999 20202020 8888888 6666666 1111111  

 1111111 是这第11大的数据。

如果结果是：2222222 3333333 4444444 7777777 5555555 10101010 9999999 20202020 8888888 6666666  就证明算法是成功的

结果：

证明算法是成功的