9. 【数据结构】TOP-K问题

文章目录

• • • 随机生成一些数据，找前k个最大值
    • 进行取前k个值建堆
    • 找到了前k个结果以及全部代码

      TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

      就是从N个数里面找最大前K个（N远大于K）

      ---

      思路一：

      • N个数插入到堆里面，PopK次

        时间复杂度是O(N*logN) + K*logN == O(N*logN)

        • N很大很大，假设N是100亿，K是10

          100亿个整数大概需要40G左右

          所以这个思路很不好~~

          ---

          思路二：

          • 读取前K个值，建立K个数的小堆

            依次再取后面的值，跟堆顶比较，如果比堆顶大，替换堆顶进堆（替换对顶值，再向下调整）

            时间复杂度是O(N*logK)

            随机生成一些数据，找前k个最大值

            • 那么我们就先要造数据，随机生成

              void CreateData()
              {
              	//造数据
              	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  
              

              • 打开项目的源文件所在的文件夹，就会有这个data.txt的文件，里面已经随机生成了10万个数字

                

                进行取前k个值建堆

                • 我们先从文件中读数据
                • 然后取前k个进行建立一个小堆
                • 读取前k个数，边读边建立小堆
                • 如果读取的整数 x 大于堆顶元素，将堆顶元素替换为 x，然后进行向下调整

                  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 error");
                  		return;
                  	}
                  	//读取前k个数
                  	//边读边建小堆
                  	/*for (int i = 0; i = 0; i--)
                  	{
                  		AdjustDown(minheap, k, i);
                  	}
                  	//读取剩余的值，读到x里
                  	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个结果以及全部代码
                   
                  

                  • 比如我取前5个最大的，我们来看一下结果

                    void AdjustUp(HPDataType* a, int child)
                    {
                    	int parent = (child - 1) / 2;
                    	while (child > 0)
                    	{
                    		if (a[child]  
                     
                    

                    • 那么我们知道这前5个是最大的吗？

                    • 这个时候就要加入我们的密探，手动从文件里加入5个最大的数~~

                      • 加入这几个数100001 100002 100003 100005 100004
                      • 然后再执行代码，可以看到已经完美的出来了~~