??

?? 博客內容：【數(shù)據(jù)結構】向上調整建堆和向下調整建堆的天壤之別以及堆排序算法

?? 作??者：陳大大陳

?? 個人簡介：一個正在努力學技術的準前端，專注基礎和實戰(zhàn)分享 ，歡迎私信！

?? 歡迎大家：這里是CSDN，我總結知識和寫筆記的地方，喜歡的話請三連，有問題請私信 ?? ?? ??

目錄

向上調整

向上調整建堆?

向下調整?

?向下調整建堆

兩種方法的天壤之別?

總結一下

堆排序?

向上調整

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{	
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			 break;
		}
	}
}

向上調整建堆?

	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}

向下調整?

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child+1< n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}

	}
}

?向下調整建堆

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

兩種方法的天壤之別?

這兩個建堆方法看似相同，實際卻有著天壤之別。

具體的數(shù)值我們可以計算一下。

如圖，二叉樹的第h層有2^(h-1)個節(jié)點。

?向下調整建堆最壞的情況就是每個節(jié)點都需要調整。

第一層有1個節(jié)點，最壞的情況是每個節(jié)點向下移動n-1層，次數(shù)就是1*(n-1)次。

第二層有2個節(jié)點，最壞的情況是每個節(jié)點向下移動n-2層，次數(shù)就是2*(n-2)次。

以此類推。。。

第n-2層有2^(n-3)個節(jié)點，最壞的情況是每個節(jié)點向下移動兩層，次數(shù)就是2^(n-3)次.

第n-1層有2^(n-2)個節(jié)點，最壞的情況是每個節(jié)點向下移動一層，次數(shù)就是2^(n-2)次。

總共的計算次數(shù)就是f(h)=2^0*(n-1)+2^1*(n-2)+……+2^(h-3)*2+2*(n-2)*1次

這個數(shù)字我們可以用錯位相減法計算出來。

最后得到的結果F(h）= 2^h?-1 - h。

假設樹的節(jié)點有N個。

那么根據(jù)公式，2 ^?h - 1= N。

把表達式往N上湊。

就得到F(N) = N - log(N+1)。

向下調整建堆的時間復雜度也就得出來了，log(N+1)的大小基本可忽略。

所以向下調整的時間復雜度是o(N)左右。

再來看向上調整建堆。

向上調整就沒有這么優(yōu)秀了。

?假設樹的高度是h,二叉樹的最后一層就占了一半的節(jié)點。

?我們仍舊按最壞的情況來算。

最后一層的每個節(jié)點都需要向上調整h-1次，光最后一層調整的次數(shù)就已經有2^(h-1)*(h-1)次了。

光看這一層可以看出差距。

上一條講的向下調整的特點是節(jié)點多的層級調整的次數(shù)少，是少乘多。

而現(xiàn)在講的向上調整恰恰相反。

節(jié)點多的層級調整的次數(shù)多，是多乘多，這就造成了時間復雜度的巨大差異。

同樣來計算一下。

假設高度為h。

F(h)=2^1*1+2^2*2+……+2^(h-2)*h-2+2^(h-1)*(h-1)

同樣使用錯位相減，解得F(h) = 2^h * (h-2) + 2

因為 N =?2^h-1。

我們將F(h)換成關于N的式子，F(xiàn)(N) = (N+1) * (log(N+1) -2 ) + 2 。??

同樣是忽略掉不重要的數(shù)據(jù)，它的時間復雜度大概是O(N*logN)。它的量級比向下調整大了很多。

所以一般情況下，我們建堆一般是用向下調整。

總結一下

建堆——向下調整建堆——時間復雜度：O(N)

建堆——向上調整建堆——時間復雜度：O(N*logN)

時間復雜度上向下調整建堆優(yōu)秀很多，我們建堆一般就使用它。

堆排序?

void HeapSort(int* a, int n)
{
	、

	//向下調整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
//向下排序
	while (end>0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a,end, 0);
		--end;
	}
}

• 將待排序序列構造成一個大堆
• 此時，整個序列的最大值就是堆頂?shù)母?jié)點。
• 將其與末尾元素進行交換，此時末尾就為最大值。
• 然后將剩余n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。如此反復執(zhí)行，便能得到一個有序序列了。
• 可以看到在構建大頂堆的過程中，元素的個數(shù)逐漸減少，最后就得到一個有序序列了
• 向下排序和上面向上調整建堆很像，時間復雜度都可以認為是O(N*logN)。

文章來源地址http://www.zghlxwxcb.cn/news/detail-463315.html

到了這里，關于【數(shù)據(jù)結構】向上調整建堆和向下調整建堆的天壤之別以及堆排序算法的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！