【数据结构】堆的TopK问题

大家好，���是苏貝，本篇博客带大家了解堆的TopK问题，如果你觉得我写的还不错的话，可以给我一个赞吗，感谢❤️

目录

• 一. 前言
• 二. TopK
• 三. 代码

  一. 前言

  TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决

  ---

  二. TopK

  思路:

  1. 用数据集合中前K个元素来建堆

     前k个最大的元素，则建小堆

     前k个最小的元素，则建大堆

  2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

  下面我们用找出1000000个元素中最大的5个值举例

  1

  为1000000个元素赋值

  1000000个元素当然不可能是由我们手动赋值，我们想到有srand函数搭配time函数可以生成随机值。

  以写的形式打开文件"data.txt"，如果文件不存在，就会建立该文件。

  我们知道，srand(time(0))能生成的随机值只有3万多个，这就意味着如果我们只用随机数赋值的话，会有将近997万的数据是重复的，所以我们在随机数的基础上再加一个会变的数，这样重复的数字就会比较少。

  最后，将随机数写入文件中。

  void CreateData(){FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");return;}int n = 1000000;srand(time(0));for (int i = 0; i  
  在上面代码的操作下，我们能保证所有的随机值都1000000，这样最后的值只能是我们修改了的。
   
  注意：
  在修改完5个值后，将调用main函数中调用CreateData函数的代码注释掉，否则再次运行程序，文件里的数据会重新被修改
   
  2
  如何建小堆？
   
  1.先定义一个指针指向k个元素的数组
  2.将文件的前k个元素边插入，边向上调整，最后得到小堆
   
  了解fscanf
   
  //void swap(int* a, int* b)//{//int tmp = *a;//*a = *b;//*b = tmp;//}//void AdjustUp(int* a, int child)//{//assert(a);////int parent = (child - 1) / 2;//while (child > 0)//{//if (a[child]  
  3
  要找出最大的k个值时，为什么不用大堆？
   
  因为如果最大值先出来，就占据了堆顶的位置，此时次大值就因为//assert(a);////int child = parent * 2 + 1;//while (child  
  三. 代码
   
  #include#include#include#include//构建数据void CreateData(){FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");return;}int n = 1000000;srand(time(0));for (int i = 0; i  0){if (a[child]  minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i   
  好了，那么本篇博客就到此结束了，如果你觉得本篇博客对你有些帮助，可以给个大大的赞吗，感谢看到这里，我们下篇博客见❤️