当前位置：首页 > news >正文

网站备案名企业名wordpress 群发插件

news 2025/11/7 9:28:45

网站备案名企业名,wordpress 群发插件,特克斯与凯科斯群岛域名官方网站,旅游网站设计的意义目录 1.解题思路2.创建一个文件并在文件中写入数据3.为什么要建立小堆而不建立大堆？4.如何在现有的数据中建立适合的大堆？5.代码实现 1.解题思路 TopK问题即是在众多数据中找出前K大的值，则可以根据堆的性质来实现，但在使用堆之前…

1.解题思路

TopK问题即是在众多数据中找出前K大的值，则可以根据堆的性质来实现，但在使用堆之前，我们要想办法先去建立一个堆，那么建立大堆还是小堆？答案是建立小堆.

2.创建一个文件并在文件中写入数据


void CreateNDate()
{// 造数据int n = 10000;srand(time(0));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;fprintf(fin, "%d\n", x);}fclose(fin);
}

3.为什么要建立小堆而不建立大堆？

假设数据的范围是1到100，如果要求找出前10大的值，如果我们建立大堆，假设第一个值正好是最大的，那么这个堆里就不会在进入其他的值了，这明显是错误的.
在这里插入图片描述

但如果建立小堆，每个元素在插入的时候与堆首元素进行比较，如果比首元素大那就替换并向下调整，这样一来，就可以实现我们想要的结果.

4.如何在现有的数据中建立适合的大堆？

我们可以根据K的不同，建立不同大小的堆，加入要找前K个值，那么我们就建立大小为K的小堆,建堆又有两种方式，即向上调整法和向下调整法，在之前的文章中我证明了向上调整法的时间复杂度是O(N*logN)而向下调整法的时间复杂度是O(N),因此如果追求时间复杂的的话，向下调整法会更好


for (int i = (k-2)/2; i < k; i++)
{AdjustDown(topK, k, i);}
/*for (int i = k - 1; i > 0; i--)
{AdjustUp(topK, i);
}*/

5.代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child+1<n&&a[child + 1] < a[child]){child++;}if (a[parent] > a[child]){Swap(&a[parent], &a[child]);}parent = child;child = parent * 2 + 1;}}
void AdjustUp(int* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[parent] > a[child]){Swap(&a[parent], &a[child]);}child = parent;parent = (child - 1) / 2;}}void CreateNDate()
{// 造数据int n = 10000;srand(time(0));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;fprintf(fin, "%d\n", x);}fclose(fin);
}
void PrintTopK(const char* file,int k)
{int* topK = (int*)malloc(sizeof(int) * k);assert(topK);FILE* fout = fopen(file, "r");//读取文件 fileif (fout == NULL) {perror("open fail");return;}for (int i = 0; i < k; i++) {fscanf(fout, "%d", &topK[i]);}for (int i = (k-2)/2; i < k; i++){AdjustDown(topK, k, i);}/*for (int i = k - 1; i > 0; i--){AdjustUp(topK, i);}*/int val = 0;int ret= fscanf(fout, "%d", &val);while (ret != EOF){if (val > topK[0]){topK[0] = val;AdjustDown(topK, k, 0);}ret = fscanf(fout, "%d", &val);}for (int i = 0; i < k; i++){printf("%d ", topK[i]);}fclose(fout);}
int main()
{CreateNDate();PrintTopK("data.txt", 10);return 0;}