一、本章重點(diǎn) 

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

二、堆

2.1堆的介紹（三點(diǎn)）

1.物理結(jié)構(gòu)是數(shù)組

2.邏輯結(jié)構(gòu)是完全二叉樹(shù)

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

2.2向上調(diào)整

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

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

以大堆為例：

邏輯實(shí)現(xiàn)：

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

如果中途孩子小于父親，則跳出循環(huán)，結(jié)束調(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]);
            //迭代過(guò)程：
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
            //如果孩子小于父親，結(jié)束調(diào)整
			break;
		}
	}
}

向上調(diào)整應(yīng)用

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

2.3向下調(diào)整

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

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

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

邏輯實(shí)現(xiàn)：

選出根的左右孩子較大的那個(gè)孩子，然后與根比較，如果比根大，則交換，否則結(jié)束調(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])//如果左孩子小于右孩子，則選右孩子
		{
			//務(wù)必加上child+1，因?yàn)楫?dāng)child=size-1時(shí)，右孩子下標(biāo)是size，對(duì)其接引用會(huì)越界訪問(wèn)。
            child++;//右孩子的下標(biāo)等于左孩子+1
		}
		if (a[child] > a[parent])//讓較大的孩子與父親比較，如果孩子大于父親，則將它們交換。
		{
			Swap(&a[child], &a[parent]);
            //迭代過(guò)程
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.4建堆（兩種方式）

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

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

參考代碼：

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

 時(shí)間復(fù)雜度計(jì)算：

以滿二叉樹(shù)進(jìn)行計(jì)算

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

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

又因?yàn)?2^h)-1=N

所以h=log(N+1)

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

因此它的時(shí)間復(fù)雜度是：O（N*logN）

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

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

參考代碼：

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

時(shí)間復(fù)雜度計(jì)算：

以滿二叉樹(shù)進(jì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

化簡(jiǎn)得T=N-log（N+1）

當(dāng)N很大時(shí)，log（N+1）可以忽略。

因此它的時(shí)間復(fù)雜度是O（N）。

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

三、堆排序

目前最好的排序算法時(shí)間復(fù)雜度是O（N*logN）

堆排序的時(shí)間復(fù)雜度是O（N*logN）

堆排序是對(duì)堆進(jìn)行排序，因此當(dāng)我們對(duì)某個(gè)數(shù)組進(jìn)行排序時(shí)，我們要先將這個(gè)數(shù)組建成堆，然后進(jìn)行排序。

首先需要知道的是：

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

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

這是為什么呢？

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

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

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

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

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

雖然這樣的時(shí)間復(fù)雜度是O（N*logN）。

但這樣的空間復(fù)雜度是O（N）。

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

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

堆排序的核心要義：

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

參考代碼：

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

整個(gè)堆排序的代碼：

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

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