堆的應(yīng)用（1000個數(shù)據(jù)中找最大的前K個元素，堆排序）

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

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

如何解決這個問題呢？我們的堆就派上用場嘍！

解題思路：

   可先創(chuàng)建一個數(shù)組topK[k],將100w中的前k個數(shù)據(jù)放入數(shù)組topK中，將topK中的數(shù)據(jù)建小堆，則可保證堆的第一個元素是最小的，將第k個元素與堆中第一個元素比較，若大于，則交換。對堆進(jìn)行重新建小堆，取第k+1個元素與堆中第一個元素比較，以此類推，直至100w-k個元素比較完。則此時堆中的元素就是k個最大數(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個元素放入數(shù)組中
	{
		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)); //隨機(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]<<" ";
	}
}

測試結(jié)果：

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

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

（2）堆排序

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

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

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

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

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

    代碼實(shí)現(xiàn)（以升序為例）：

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);
	}
}

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

測試結(jié)果：