一、本章重點 

• 堆
• 向上調(diào)整
• 向下調(diào)整
• 堆排序

二、堆

2.1堆的介紹（三點）

1.物理結構是數(shù)組

2.邏輯結構是完全二叉樹

3.大堆:所有的父親節(jié)點都大于等于孩子節(jié)點，小堆：所有的父親節(jié)點都小于等于孩子節(jié)點。

2.2向上調(diào)整

概念：有一個小/大堆，在數(shù)組最后插入一個元素，通過向上調(diào)整，使得該堆還是小/大堆。

使用條件：數(shù)組前n-1個元素構成一個堆。

以大堆為例：

邏輯實現(xiàn)：

將新插入的最后一個元素看做孩子，讓它與父親相比，如果孩子大于父親，則將它們交換，將父親看做孩子，在依次比較，直到孩子等于0結束調(diào)整·。

如果中途孩子小于父親，則跳出循環(huán)，結束調(diào)整。

參考代碼：

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
		{
            //如果孩子小于父親，結束調(diào)整
			break;
		}
	}
}

向上調(diào)整應用

給大\小堆加入新的元素之后仍使得大\小堆還是大\小堆。

2.3向下調(diào)整

概念：根節(jié)點的左右子樹都是大\小堆，通過向下調(diào)整，使得整個完全二叉樹都是大\小堆。

使用條件：根節(jié)點的左右子樹都是大\小堆。

 如圖根為23，它的左右子樹都是大堆，但整顆完全二叉樹不是堆，通過向下調(diào)整可以使得整顆完全二叉樹是堆。

邏輯實現(xiàn)：

選出根的左右孩子較大的那個孩子，然后與根比較，如果比根大，則交換，否則結束調(diào)整。

參考代碼：

void AdjustDown(HPDataType* a, int size, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//左孩子
	while (child < size)
	{
		if (child + 1 < size && a[child] < a[child + 1])//如果左孩子小于右孩子，則選右孩子
		{
			//務必加上child+1，因為當child=size-1時，右孩子下標是size，對其接引用會越界訪問。
            child++;//右孩子的下標等于左孩子+1
		}
		if (a[child] > a[parent])//讓較大的孩子與父親比較，如果孩子大于父親，則將它們交換。
		{
			Swap(&a[child], &a[parent]);
            //迭代過程
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.4建堆（兩種方式）

第一種：向上調(diào)整建堆（時間復雜度是O（N*logN），空間復雜度O（1））

思路是：從第二個數(shù)組元素開始到最后一個數(shù)組元素依次進行向上調(diào)整。

參考代碼：

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

 時間復雜度計算：

以滿二叉樹進行計算

最壞情況執(zhí)行步數(shù)為：T=(2^1)*1+(2^2)*2+(2^3)*3+....+2^(h-1)*(h-1)

最后化簡得：T=2^h*(h-2)+2

又因為(2^h)-1=N

所以h=log(N+1)

帶入后得T=(N+1)*(logN-1)+2

因此它的時間復雜度是：O（N*logN）

第二種：向下調(diào)整建堆（時間復雜度是O（N），空間復雜度是O（1））

從最后一個非葉子節(jié)點（最后一個數(shù)組元素的父親）開始到第一個數(shù)組元素依次進行向下調(diào)整。

參考代碼：

//n代表數(shù)組元素個數(shù)，j的初始值代表最后一個元素的父親下標
for (int j = (n - 1 - 1) / 2; j >= 0; j--)
{
	AdjustDown(a, n, j);
}

時間復雜度計算：

以滿二叉樹進行計算

最壞執(zhí)行次數(shù)：

T=2^(h-2)*1+2^(h-3)*2+2^(h-4)*3+.....+2^3*(h-4)+2^2*(h-3)+2^1*(h-2)+2^0*(h-1)

聯(lián)立2^h-1=N

化簡得T=N-log（N+1）

當N很大時，log（N+1）可以忽略。

因此它的時間復雜度是O（N）。

因此我們一般建堆采用向下調(diào)整的建堆方式。

三、堆排序

目前最好的排序算法時間復雜度是O（N*logN）

堆排序的時間復雜度是O（N*logN）

堆排序是對堆進行排序，因此當我們對某個數(shù)組進行排序時，我們要先將這個數(shù)組建成堆，然后進行排序。

首先需要知道的是：

對數(shù)組升序，需要將數(shù)組建成大堆。

對數(shù)組降序，需要將數(shù)組建成小堆。

這是為什么呢？

這需要明白大堆和小堆的區(qū)別，大堆堆頂是最大數(shù)，小堆堆頂是最小數(shù)。

當我們首次建堆時，建大堆能夠得到第一個最大數(shù)，然后可以將它與數(shù)組最后的元素進行交換，下一次我們只需要將堆頂?shù)臄?shù)再次進行向下調(diào)整，可以再次將數(shù)組變成大堆，然后與數(shù)組的倒數(shù)第二個元素進行交換，自此已經(jīng)排好了兩個元素，使得它們存儲在需要的地方，然后依次進行取數(shù)，調(diào)整。

而如果是小堆，首次建堆時，我們能夠得到最小的數(shù)，然后將它放在數(shù)組第一個位置，然后你要保持它還是小堆，該怎么辦呢？只能從第二個元素開始從下建堆，而建堆的時間復雜度是O（N），你需要不斷重建堆，最終堆排序的時間復雜度是O（N*N），這是不明智的。

或者建好小堆后，你這樣做:

在開一個n個數(shù)組的空間，選出第一個最小數(shù)就將它放在新開辟的數(shù)組空間中保存，然后刪除堆頂數(shù)，再通過向下調(diào)整堆頂?shù)臄?shù)，再將新堆頂數(shù)放在新數(shù)組的第二個位置.......。

雖然這樣的時間復雜度是O（N*logN）。

但這樣的空間復雜度是O（N）。

也不是最優(yōu)的堆排序方法。

而建大堆的好處就在它把選出的數(shù)放在最后，這樣我們就可以對堆頂進行向下調(diào)整，使得它還是大堆，而向下調(diào)整的時間復雜度是O(logN)，最終堆排序的時間復雜度是O（N*logN）。

堆排序的核心要義：

通過建大堆或者小堆的方式，選出堆中最大或者最小的數(shù)，從后往前放。

參考代碼：

    int end = n - 1;//n代表數(shù)組元素的個數(shù)
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}

整個堆排序的代碼：

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
 
void AdjustUp(int* 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;
		}
	}
}
void AdjustDown(int* a, int n, int root)
{
	int child = 2 * root + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child+1])
		{
			child++;
		}
		if (a[child] > a[root])
		{
			Swap(&a[child], &a[root]);
			root = child;
			child = 2 * root + 1;
		}
		else
		{
			break;
		}
	}
}
 
void HeapSort(int* a, int n)
{
	//建大堆(向上調(diào)整)
	//for (int i = 1; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}
 
	//建大堆(向下調(diào)整)
	for (int j = (n - 1 - 1) / 2; j >= 0; j--)
	{
		AdjustDown(a, n, j);
	}
	//升序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}
void printarr(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
 
int main()
{
	int arr[10] = { 9,2,4,8,6,3,5,1,10 };
	int size = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, size);
	printarr(arr, size);
	return 0;
}

到此這篇關于C語言數(shù)據(jù)結構中堆排序的分析總結的文章就介紹到這了,更多相關C語言 堆排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論