首页 > 代码库 > 求数组最大k个数的问题（堆的应用）

求数组最大k个数的问题（堆的应用）

2024-07-20 04:17:33   220人阅读

1 无顺序的一个数组求最大的k个数

1）笨方法，先用快速排序对数组排序在找前k个;
2)  用堆，先建立k小顶堆，再扫描整个数组，堆顶为k个数中最小的数；
/************************************/
//寻找在数组中最大的K个数 
//小顶堆插入
void constructHeap(int a[],int n,int value){

	a[n] = value;
	int j,temp = value;
	j = (n-1)/2;
	while (j>=0 && n!=0)
	{
		if(a[j] <= temp)
			break;
		a[n] = a[j];
		n = j;
		j = (n-1)/2;
	}
	a[n] = temp;
}
//堆更新
void UpdataHeap(int a[],int index,int n)
{
	int j,temp = a[index];
	j = 2*index + 1;
	while (j < n)
	{
		if(j+1 < n && a[j+1] < a[j])
			++j;
		if(a[j] >= temp)
			break;
		a[index] = a[j];
		index = j;
		j = index*2 +1;
	}
	a[index] = temp;
}
void MaxK(int a[],int n,int k){

	int i;
	int *temp = new int[k];
	for (i=0;i<n;++i)
	{
		if(i < k)
			constructHeap(temp,i,a[i]);//先构造k堆
		else
		{
			if (temp[0] < a[i])
			{
				temp[0] = a[i];
				UpdataHeap(temp,0,k);//更新k堆；
			}
		}
	}
	for (i=0;i<k;++i)
	{
		cout<<temp[i]<<" ";
	}
	delete []temp;
}

2 求N个降序数组的K个最大的数

http://www.cnblogs.com/ywl925/p/3794852.html

1. 建立大顶堆，维度为数组的个数，这里为20（第一次 插入的是每个数组中最大的值，即第一个元素）。

2. 删除最大堆堆顶，保存到数组或者栈中，然后向最大堆插入删除的元素所在数组的下一个元素。

3. 重复第1,2个步骤，直到删除个数为最大的K个数，这里为500.

/************************************/
//N个降序数组，找到最大的K个数
//大顶堆
void constructHeap1(int a[],int n,int value){

	a[n] = value;
	int j,temp = value;
	j = (n-1)/2;
	while (j>=0 && n!=0)
	{
		if(a[j] >= temp)
			break;
		a[n] = a[j];
		n = j;
		j = (n-1)/2;
	}
	a[n] = temp;
}
//堆更新
void UpdataHeap1(int a[],int index,int n)
{
	int j,temp = a[index];
	j = 2*index + 1;
	while (j < n)
	{
		if(j+1 < n && a[j+1] > a[j])
			++j;
		if(a[j] <= temp)
			break;
		a[index] = a[j];
		index = j;
		j = index*2 +1;
	}
	a[index] = temp;
}
void GetMaxK(){
	const int rows = 20;
	const int cols = 500;
	const int K = 500;
	int data[rows][cols];
	int result[K];//前500
	int heap[20];//堆
	int i,j;
	for (i=0;i<rows;++i)
	{
		for (j=0;j<cols;++j )
		{
			data[i][j] = rand();
		}
	}
	//快速排序
	for (i = 0;i<rows;++i)
	{
		QuikSortDown(data[i],0,cols-1);
	}
	//开始
	for(j=0;j<cols;++j)
	{
		for (i=0;i<rows;++i)
		{
			if(0 == j)
				constructHeap1(heap,i,data[i][0]);//创建堆
			else{
				if((j-1)*rows + i >K-1 )
					break;
				result[(j-1)*rows + i] = heap[0];
				heap[0] = data[i][j];
				UpdataHeap1(heap,0,20);//更新堆
			}
		}
	}
	for (i=0;i<K;++i)
	{
		cout<<result[i]<<" "<<endl;
	}
}




求数组最大k个数的问题（堆的应用）


联系
我们