找出N个数据中的最大的K个数据---堆排序

   从N个数据中找出最大的K个数据，而且这里有一个限制：内存里存不下所有的N个数据，但是可以存下K个数据。这就让我们打消了用排序的方法来解的念头。

   在这里我们使用堆排序来完成。

  因为我们只能有K个数据那么大的空间，所以我们建一个K大的堆，将N的前K个数据插入到堆中，然后调整堆。（对于堆结构不了解的可以查看我微博  http://helloleex.blog.51cto.com/10728491/1768758）

  对于最大的K个数据，我们要怎么找出来呢。我们首先要确定我们是要用大顶堆还是小顶堆。

•  用大顶堆。用大顶堆的话我们一定可以确定N个数据中最大的1个数据或者多个，但是一定不会是最大K个，因为我们只有K大的内存，所以每次往堆里插入数据同时就要删除一个数据，而删除数据只能删除最大的那一个。到最后大的数据都被Pop完了

• 用小顶堆。用小顶堆就可以完美的解决这个问题，每次从N个数据中的后N-K个数据插入一个数据到大小为K的堆中替换掉小顶堆的根（最小值）。最后的K个数据就是最大的K个数据。

• #include"windows.h"
  #include"time.h"
  #include"head.h"
  //堆排序
  void AdjustDown(int* a, size_t size, size_t parent)//下调函数
  {
  	size_t child = parent * 2 + 1;
  	while (child < size)
  	{
  		if (child + 1 < size&&a[child] < a[child + 1])
  			++child;
  		if (a[parent] < a[child])
  		{
  			swap(a[parent], a[child]);
  			parent = child;
  			child = parent * 2 + 1;
  		}
  		else
  			break;
  	}
  }
  
  void HeapSort(int* a, size_t size)
  {
  	//建堆
  	for (int i = (size - 2) / 2; i >= 0; --i)
  		//i不能定义为size_t除法会溢出，翻转成一个很大的数
  	{
  		AdjustDown(a, size, i);
  	}
  	for (size_t i = 0; i < size; ++i)
  	{
  		swap(a[0], a[size - 1 - i]);
  		AdjustDown(a, size - i - 1, 0);
  	}
  }
  
  
  void FindMaxK(int N,int K)//找出N个数据中最大的K个数据
  {
  	int* arryN = new int[N];
  	int* maxK = new int[K];
  	for (int i = 0; i < N; ++i)
  	{
  		arryN[i] = (rand() % 100);
  	}
  	for (int i = 0; i < N; ++i)
  	{
  		cout << arryN[i] << " ";
  	}
  	cout << endl;
  	for (int i = 0; i < K; i++)
  	{
  		maxK[i] = arryN[i];
  	}
  	for (int i = K; i < N; ++i)
  	{
  		HeapSort(maxK, K);
  		maxK[0] = arryN[i];
  	}
  	for (int i = 0; i < K; ++i)
  	{
  		cout << maxK[i] << " ";
  	}
  }

  AI代码助手复制代码

  堆排序的时间效率是nlogn，算是效率比较高的算法了，值得我们去掌握的。

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>