堆的應(yīng)用（1000個(gè)數(shù)據(jù)中找最大的前K個(gè)元素，堆排序）-創(chuàng)新互聯(lián)

(1)從1000個(gè)數(shù)據(jù)中找到k個(gè)大數(shù)據(jù)

創(chuàng)新互聯(lián)專(zhuān)注于儀隴企業(yè)網(wǎng)站建設(shè),成都響應(yīng)式網(wǎng)站建設(shè)公司,購(gòu)物商城網(wǎng)站建設(shè)。儀隴網(wǎng)站建設(shè)公司,為儀隴等地區(qū)提供建站服務(wù)。全流程按需求定制開(kāi)發(fā)，專(zhuān)業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)專(zhuān)業(yè)和態(tài)度為您提供的服務(wù)

首先看到這個(gè)題時(shí)，可能會(huì)想到先將這1000個(gè)數(shù)據(jù)進(jìn)行降序排序，即取出的前k個(gè)元素大。時(shí)間復(fù)雜度為O（N^2）,使得程序效率低。

如何解決這個(gè)問(wèn)題呢？我們的堆就派上用場(chǎng)嘍！

解題思路：

 可先創(chuàng)建一個(gè)數(shù)組topK[k],將100w中的前k個(gè)數(shù)據(jù)放入數(shù)組topK中，將topK中的數(shù)據(jù)建小堆，則可保證堆的第一個(gè)元素是最小的，將第k個(gè)元素與堆中第一個(gè)元素比較，若大于，則交換。對(duì)堆進(jìn)行重新建小堆，取第k+1個(gè)元素與堆中第一個(gè)元素比較，以此類(lèi)推，直至100w-k個(gè)元素比較完。則此時(shí)堆中的元素就是k個(gè)大數(shù)據(jù)。

 代碼實(shí)現(xiàn)：

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個(gè)元素放入數(shù)組中
	{
		topK[i] = a[i];
	}
	for(i=(K-2)/2;i>=0;--i)//對(duì)前K個(gè)元素建小堆
	{
		AdjustDown(topK,i);
	}
	for(i=K;i<N;++i)
	{
		if(a[i] > topK[0]) //將K個(gè)元素之后的每個(gè)元素和堆的第一個(gè)元素(最小元素)比較
		{
			swap(a[i],topK[0]);//若比第一個(gè)元素大，則交換
			AdjustDown(topK,0);//對(duì)新堆重新建小堆
		}
	}
}

測(cè)試代碼：

void Test2()
{
	int topK[K];
	int a[N];
	srand(time(0)); //隨機(jī)數(shù)種子
	for(int i=0;i<N;++i)
	{
		a[i] = rand(); //隨機(jī)數(shù)
	}
	GetTopK(a,topK);
	for(int i=0;i<K;i++)
	{
		cout<<topK[i]<<" ";
	}
}

測(cè)試結(jié)果：

時(shí)間復(fù)雜度為 k*lgk+N*lgk

當(dāng)N龐大時(shí)，k可忽略，則時(shí)間復(fù)雜度為O（N），大大提高了效率。

（2）堆排序

既然是排序，那就有兩種可能升序or降序。使得堆是建大堆方便還是建小堆方便。

<1>若為升序，則需要建大堆。

  堆的第一個(gè)元素為大，將大元素與末尾元素交換，剩下的元素（除末尾元素）向下調(diào)整。

<2>若為降序，則需要建小堆。

  堆的第一個(gè)元素為最小，將最小元素與末尾元素交換，剩下的元素（除末尾元素）向下調(diào)整。

  代碼實(shí)現(xiàn)（以升序?yàn)槔?/p>

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);  //建大堆
	}

	//選擇大的放到末尾，從剩下數(shù)據(jù)向下調(diào)整
	for(int i=0;i<size;i++)
	{
		swap(a[0],a[size-1-i]);
		AdjustDown(a,0,size-1-i);
	}
}

//測(cè)試代碼
void TestHeapSort()
{
	int a[] = {10,16,18,12,11,13,15,17,14,19};
	int size = sizeof(a)/sizeof(a[0]);
	HeapSort(a,size);	
}

測(cè)試結(jié)果：

創(chuàng)新互聯(lián)www.cdcxhl.cn，專(zhuān)業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開(kāi)啟，新人活動(dòng)云服務(wù)器買(mǎi)多久送多久。

文章名稱(chēng)：堆的應(yīng)用（1000個(gè)數(shù)據(jù)中找最大的前K個(gè)元素，堆排序）-創(chuàng)新互聯(lián)
網(wǎng)站網(wǎng)址：http://muchs.cn/article40/dhsieo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、網(wǎng)站維護(hù)、虛擬主機(jī)、品牌網(wǎng)站制作、企業(yè)建站、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)