堆的应用（1000个数据中找最大的前K个元素，堆排序）-创新互联

(1)从1000个数据中找到k个大数据

首先看到这个题时，可能会想到先将这1000个数据进行降序排序，即取出的前k个元素大。时间复杂度为O（N^2）,使得程序效率低。

如何解决这个问题呢？我们的堆就派上用场喽！

解题思路：

 可先创建一个数组topK[k],将100w中的前k个数据放入数组topK中，将topK中的数据建小堆，则可保证堆的第一个元素是最小的，将第k个元素与堆中第一个元素比较，若大于，则交换。对堆进行重新建小堆，取第k+1个元素与堆中第一个元素比较，以此类推，直至100w-k个元素比较完。则此时堆中的元素就是k个大数据。

 代码实现：

const int N = 1000;
const int K = 100;

void AdjustDown(int topK[],int parent) //建小堆
{
	int child = 2*parent+1;
	while(child < K)
	{
		if(child+1 < K && topK[child+1] < topK[child])
		{
			++child;
		}
		if(topK[child] < topK[parent])
		{
			swap(topK[child],topK[parent]);
			parent = child;
			child = 2*parent+1;
		}
		else
		{
			break;
		}
	}
}
void GetTopK(int a[],int topK[])
{
	assert(a);
	int i = 0;
	for(i=0;i=0;--i)//对前K个元素建小堆
	{
		AdjustDown(topK,i);
	}
	for(i=K;i topK[0]) //将K个元素之后的每个元素和堆的第一个元素(最小元素)比较
		{
			swap(a[i],topK[0]);//若比第一个元素大，则交换
			AdjustDown(topK,0);//对新堆重新建小堆
		}
	}
}

测试代码：

void Test2()
{
	int topK[K];
	int a[N];
	srand(time(0)); //随机数种子
	for(int i=0;i
测试结果：
时间复杂度为 k*lgk+N*lgk 
当N庞大时，k可忽略，则时间复杂度为O（N），大大提高了效率。
（2）堆排序
既然是排序，那就有两种可能升序or降序。使得堆是建大堆方便还是建小堆方便。
<1>若为升序，则需要建大堆。
  堆的第一个元素为大，将大元素与末尾元素交换，剩下的元素（除末尾元素）向下调整。
<2>若为降序，则需要建小堆。
  堆的第一个元素为最小，将最小元素与末尾元素交换，剩下的元素（除末尾元素）向下调整。
  代码实现（以升序为例）：
void AdjustDown(int a[],int parent,int size)  //建大堆
{
	assert(a);
	int child = 2*parent+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 = 2*parent+1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int a[],int size) 
{
	assert(a);
	//建堆
	for(int i=(size-2)/2;i>=0;--i)
	{
		AdjustDown(a,i,size);  //建大堆
	}

	//选择大的放到末尾，从剩下数据向下调整
	for(int i=0;i
测试结果：
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
            

            文章标题：堆的应用（1000个数据中找最大的前K个元素，堆排序）-创新互联            

            文章链接：http://cqcxhl.cn/article/dhsieo.html