【TopK问题】——用堆实现

文章目录

• 一、TopK问题是什么
• 二、解决方法
• 三、时间复杂度

  一、TopK问题是什么

  TopK问题就是从1000个数中找出前K个最大的数或者最小的数这样的类似问题。

  
  （图片来源网络，侵删）

  不过并不要求这k个数字必须是有序的，如果题目有要求，则进行堆排序即可。

  还有比如求出全国玩韩信前十名等等，排出班级前十名也是TopK问题。

  二、解决方法

  采用堆的方式可以较快解决。

  思路：如果需要排前k个最大的数，则需要建一个小堆

  如果需要排前k个最小的数，则需要建一个大堆

  假设现在需要排序前k个最大的数，则需要建立一个小堆。

  建立小堆是拿n个数的前k个数来建立的。

  不能把n个数全部建立成一个小堆，这样效率会大打折扣，因为通过向下调整建堆的时间复杂度是O(N)，假如要从10亿个数字中排前50个最大的，那么建立一个10亿个数大小的堆，开销还是比较大的。

  建立了一个小堆后，此时堆顶元素是最小的，

  从第k+1个数开始，只要第K+1个数大于堆顶元素，就将该数字于堆顶元素进行交换，然后再向下调整。

  这样做的结果是：只要我比堆顶元素大，我就进堆，如果我在堆中是比较大的，我就会“下沉”到堆底，（因为这是一个小堆）。

  这样遍历多次后，原来堆中的元素会被换成新的一批更大一点的元素。

  当我们遍历完n个数后，留在堆中的一定是前k个最大的数。

  代码如下：

  随机生成10个1000以内的数字，求这10个数字的最大的3个：

  void AdjustDown(HPDataType* a, int n, int parent)
  {
  	//假设左孩子就是最大的
  	int child = (parent * 2) + 1;
  	while (child a[child]),不能这样判断
  		//(因为有可能存在右孩子不存在的情况，需要判断一下右孩子是否存在)
  		//否则容易出现越界问题
  //		if (a[child + 1] > a[child] && child + 1  a[child])
  		{
  			child++;
  		}
  		//大孩子和父节点交换
  		if (a[child] > a[parent])
  		{
  			swap(&a[child], &a[parent]);
  			//交换之后往下走，
  			parent = child;
  			child = (parent * 2) + 1;
  		}
  		else
  		{
  			break;
  		}
  	}
  }
  void Find_TopK(int* a, int n ,int k)
  {
  	assert(a!=NULL);
  	assert(k > 0);
  	int* topk = (int*)malloc(sizeof(int) * k);
  	assert(topk);
  	for (int i = 0; i = 0; i--)
  	{
  		AdjustDown(topk, k, i);
  	}
  	//2.然后从第k个开始，往堆里面插入
  	int j = k;
  	while (j  topk[0])
  		{
  			topk[0] = a[j];
  			AdjustDown(topk, k, 0);
  		}
  		j++;
  	}
  	printf("这10个数中最大的3个数为：\n");
  	for (int i = 0; i  
  三、时间复杂度
   
  建堆的时间复杂度:O(K)
  遍历的时间复杂度:O(N-K)
  每次遍历调整的时间复杂度:O(logK)
  总的时间复杂度O(K+(N-K)logK) ≈ O(NlogK)