快捷導(dǎo)航

C語言關(guān)于二叉樹中堆的創(chuàng)建和使用整理

更新時間：2022年08月03日 10:51:58 作者：Rookiep

大家好,這里是針對二叉樹中堆結(jié)構(gòu)的順序儲存，整理出來一篇博客供我們一起復(fù)習(xí)和學(xué)習(xí),如果文章中有理解不當(dāng)?shù)牡胤?還希望朋友們在評論區(qū)指出,我們相互學(xué)習(xí),共同進步

一、堆的創(chuàng)建

下面我們先看一段代碼：

void HeapSort(int* a, int size)
{
	// 建小(da)堆
	HP hp;
	HeapInit(&hp);
	// O(N*logN)
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);// O(N)空間復(fù)雜度
	}
	HeapPrint(&hp);
	// O(N*logN)  排序
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}

這是一段堆排序的算法，從代碼中我們可以看出，當(dāng)傳入一個數(shù)組時，我們申請了額外一塊空間來創(chuàng)建堆，這時空間復(fù)雜度為O(N),這顯然存在缺陷，需要改進！

下面我們介紹兩種調(diào)整算法來創(chuàng)建堆，就在原數(shù)組空間上進行堆的創(chuàng)建，空間復(fù)雜度為O(1)!

1、向上調(diào)整算法建堆

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

代碼解釋：在數(shù)組中從第二個元素出發(fā)，在邏輯上依次進行向上調(diào)整。

向上調(diào)整建堆方式對于建大堆還是小堆關(guān)鍵在于AdjustUp函數(shù)。

void AdjustUp(HPDataType* a, HPDataType child){
	assert(a);
	//int child = php->size - 1;
	int parent = (child - 1) / 2;
	while (a[parent] > a[child] && parent >= 0)//小堆!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	{
		Swap(&a[parent], &a[child]);
		child = parent;
		parent = (child - 1) / 2;
	}
}

while (a[parent] < a[child] && parent >= 0)//大堆?。。。。。。。。。。。。。。。。。。?
	{
		Swap(&a[parent], &a[child]);
		child = parent;
		parent = (child - 1) / 2;
	}

2、向下調(diào)整算法建堆

注意：向下調(diào)整時，必須保證子樹都是堆，所以從最后一個非葉子節(jié)點（最后一個節(jié)點的父親）開始依次進行向下調(diào)整算法！

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

代碼解釋：在數(shù)組中從第(n - 1 - 1) / 2個元素出發(fā)，在邏輯上依次進行向下調(diào)整。

向下調(diào)整建堆方式對于建大堆還是小堆關(guān)鍵在于AdjustDown函數(shù)。

建小堆：

void AdjustDown(HPDataType* a, size_t size, size_t root){
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		//選出左右孩子小的那一個
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		//向下調(diào)整，如果孩子小于父親，則交換，繼續(xù)向下調(diào)整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

建大堆：

while (child < size)
	{
		//選出左右孩子大的那一個
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}
		//向下調(diào)整，如果孩子da于父親，則交換，繼續(xù)向下調(diào)整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

兩種創(chuàng)建方式的區(qū)別：

主要在于時間復(fù)雜度上：

向上調(diào)整算法的時間復(fù)雜度是O(N * log N);
向下調(diào)整算法的時間復(fù)雜度是O(N);

所以常選用向下調(diào)整算法！

二、堆排序

堆排序即利用堆的思想來進行排序，總共分為兩個步驟：

1、建堆

升序：建大堆
降序：建小堆

2、利用堆刪除思想來進行排序

建堆和堆刪除都用到了向下調(diào)整算法，因此掌握了向下調(diào)整，就可以完成堆排序！

void HeapSort(int * a, int n){
	assert(a);
	//向上調(diào)整--建堆   向上建堆的復(fù)雜度比向下的高
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	//向下調(diào)整，必須保證子樹都是堆，所以從后往前
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);//這里的函數(shù)是對應(yīng)上文的建小堆的AdjustDown函數(shù)
	}//小堆--對應(yīng)降序排列
	
	size_t end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);//這里的函數(shù)是對應(yīng)上文的建小堆的AdjustDown函數(shù)
		--end;
	}
}
int main()
{
	//TestHeap();
	int a[] = { 4, 2, 7, 8, 5, 1, 0, 6 };
	HeapSort(a, sizeof(a) / sizeof(int));

	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}