温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

堆的应用(1000个数据中找最大的前K个元素,堆排序)

发布时间:2020-07-08 03:19:22 来源:网络 阅读:1095 作者:下一个明天 栏目:编程语言

(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<K;++i) //将a的前K个元素放入数组中
	{
		topK[i] = a[i];
	}
	for(i=(K-2)/2;i>=0;--i)//对前K个元素建小堆
	{
		AdjustDown(topK,i);
	}
	for(i=K;i<N;++i)
	{
		if(a[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<N;++i)
	{
		a[i] = rand(); //随机数
	}
	GetTopK(a,topK);
	for(int i=0;i<K;i++)
	{
		cout<<topK[i]<<" ";
	}
}

测试结果:

堆的应用(1000个数据中找最大的前K个元素,堆排序)

时间复杂度为 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<size;i++)
	{
		swap(a[0],a[size-1-i]);
		AdjustDown(a,0,size-1-i);
	}
}

//测试代码
void TestHeapSort()
{
	int a[] = {10,16,18,12,11,13,15,17,14,19};
	int size = sizeof(a)/sizeof(a[0]);
	HeapSort(a,size);	
}

测试结果:

堆的应用(1000个数据中找最大的前K个元素,堆排序)

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI