一.Top-K问题

#include<stdio.h>
//先自主创建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;//生成n个100000以内的数据fprintf(fin, "%d\n", x);//写入文件}fclose(fin);//关闭文件
}
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个数据}// 建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);
}//向下调整算法（具体函数内部结构参数可以参考我上一篇文章，即二叉树的数组结构）
void AdjustDown(HP* hp, int parent, int n)//n是向下调整的下界范围
{int child = parent * 2 + 1;//公式while (child < n){//建小根堆if (child + 1 < n && hp->arr[child + 1] < hp->arr[child])//child+1的目的是确保两个孩子结点都是有意义的结点{child++;}if (hp->arr[parent] > hp->arr[child]){swap(&hp->arr[parent], &hp->arr[child]);parent = child;child = parent * 2 + 1;}else{//我最小的孩子都比父节点大，那么这个堆就是正常堆了，直接退出break;}}
}