本文主要是介绍利用 堆 找出10万个数字中的最大的前 k 个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、思路
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 就证明算法是成功的
结果：
证明算法是成功的
这篇关于利用 堆 找出10万个数字中的最大的前 k 个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
