新网站建设运营年计划书,合肥专业网站优化费用,盐城seo网站优化软件,睢宁县凌城做网站的问题描述
TOP-K问题#xff1a;即求数据结合中前K个最大的元素或者最小的元素#xff0c;一般情况下数据量都比较大 比如#xff1a;专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等 对于Top-K问题#xff0c;能想到的最简单直接的方式就是排序#xff0c;但是即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下 1. 用数据集合中前K个元素来建堆
前k个最大的元素则建小堆 前k个最小的元素则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素
算法思路
大致的实现代码是这样 数据量非常非常大的时候比如在文件中有1000000000个值找出最大的前十个
这时我们不可能建大堆去pop 10次太消耗内存了
我们的思路是假如TopK
创建数据到文件中读取文件前k个值构建一个k个数的小堆读取文件剩下的值与堆顶的数比较如果比堆顶数值大那就替换他并向下调整打印前k个数据
1.创建数据到文件中 这里我们创建数据的时候%了10000000保证数据都是在10000000以内的
我们创建的文件就在文件夹中 2.并构建一个k个数的小堆 3.读取文件剩下的值 总代码
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include time.h
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 *p1;
}
void AdjustUp(int* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}elsebreak;}
}
void CreatNDate()
{//造数据int n 10000000;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) % 10000000;fprintf(fin, %d\n, x);}fclose(fin);
}
void PrintTopK(const char* file, int k)
{FILE* fout fopen(file, r);if (fout NULL){perror(fopen error);return;}//建一个k个数的小堆int* minheap (int*)malloc(sizeof(int) * k);if (minheap NULL){perror(malloc fail);return;}//读取前k个数for (int i 0; i k; i){fscanf(fout, %d, minheap[i]);//建小堆AdjustUp(minheap, 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]);}printf(\n);fclose(fout);
}
int main()
{//CreatNDate();PrintTopK(data.txt, 5);return 0;
}
结果我们就可以找出前k个值了
