搬瓦工的主机可以用来做网站吗,seo工具在线访问,wordpress如何设置注册,h5免费模板下载目录 1.解题思路2.创建一个文件并在文件中写入数据3.为什么要建立小堆而不建立大堆#xff1f;4.如何在现有的数据中建立适合的大堆#xff1f;5.代码实现 1.解题思路
TopK问题即是在众多数据中找出前K大的值#xff0c;则可以根据堆的性质来实现#xff0c;但在使用堆之前… 目录 1.解题思路2.创建一个文件并在文件中写入数据3.为什么要建立小堆而不建立大堆4.如何在现有的数据中建立适合的大堆5.代码实现 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
#includestdio.h
#includestdlib.h
#includeassert.h
#includetime.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 (child1na[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;}
实际上我们可以看出虽然建堆的时间复杂度可以优化但是后面的从文件中读取数据并进行判断是否替换的过程是无法进行优化的时间复杂度为O(N*logN),因此建堆的时间复杂度并不影响整个算法的时间复杂度
结尾今天的分享到此结束喜欢的朋友如果感觉有帮助可以点赞三连支持咱们共同进步!
