1.堆的概念結(jié)構(gòu)及分類

以上這段概念描述看起來十分復(fù)雜，晦澀難懂。那么堆用通俗語言簡(jiǎn)單描述如下：

堆是一個(gè)完全二叉樹的順序存儲(chǔ)。在一個(gè)堆中，堆的父節(jié)點(diǎn)一定大于等于(或小于等于)子節(jié)點(diǎn)。一旦有一部分不滿足則不為堆。

堆的性質(zhì)： 

1、堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
2、堆總是一棵完全二叉樹

1.2堆的分類

1.2.1 大堆

在一個(gè)堆中，父節(jié)點(diǎn)一定大于等于子節(jié)點(diǎn)的堆稱為大堆。又稱大根堆。

1.2.2 小堆

在一個(gè)堆中，父節(jié)點(diǎn)一定小于等于子節(jié)點(diǎn)的堆稱為小堆。又稱小根堆。(下圖就是一個(gè)小堆)

習(xí)題練習(xí)：

1.下列關(guān)鍵字序列為堆的是：（A）
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32

分析：選項(xiàng)A分析后為大堆，其他選項(xiàng)多多少少都存在錯(cuò)誤。（畫圖分析如下）

2. 堆的主要接口

在本篇文章中我們主要以小堆為例實(shí)現(xiàn)。

現(xiàn)實(shí)中我們通常把堆使用順序結(jié)構(gòu)的數(shù)組來存儲(chǔ)，需要注意的是這里的堆和操作系統(tǒng) 虛擬進(jìn)程地址空間中的堆是兩回事，一個(gè)是數(shù)據(jù)結(jié)構(gòu)，一個(gè)是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。

其中堆中包括以下主要功能：

1.堆的初始化   2.堆銷毀  3.堆打印  4.堆的插入元素  5.堆刪除元素   6.判斷堆是否為空  7.求堆中元素的個(gè)數(shù)  8.求堆頂元素

詳細(xì)接口如下：

//小堆
//算法邏輯思想是二叉樹，物理上操作的是數(shù)組中數(shù)據(jù)
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;   //數(shù)組a
	size_t size;     //下標(biāo)
	size_t capacity; //容量
}HP;
 
void Swap(HPDataType* pa, HPDataType* pb);//交換函數(shù)
void HeapInit(HP* php);//堆初始化
void HeapDestory(HP* php);//堆銷毀
void HeapPrint(HP* php);//堆打印
 
//插入x以后，仍然要保證堆是（大/?。┒?
void HeapPush(HP* php, HPDataType x);
 
//刪除堆頂?shù)臄?shù)據(jù)（最大/最?。?
void HeapPop(HP* php);
 
bool HeapEmpty(HP* php); //判斷是否為空
size_t HeapSize(HP* php);//求元素個(gè)數(shù)
HPDataType HeapTop(HP* php);//求堆頂元素

3.堆的實(shí)現(xiàn)

有了如上的接口，接下來我們實(shí)現(xiàn)各個(gè)接口。由于我們使用數(shù)組來實(shí)現(xiàn)堆，大多接口功能和順序表的實(shí)現(xiàn)相同。相同的實(shí)現(xiàn)這里不再過多分析。

3.1 堆的初始化 HeapInit

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
 
}

3.2 堆的銷毀 HeapDestory

void HeapDestory(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
 
}

3.3 堆的打印 HeapPrint

void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

3.4 堆的插入元素 HeapPush   *

堆的元素插入是堆的一大重點(diǎn)和難點(diǎn)。接下來我們對(duì)該功能進(jìn)行分析和實(shí)現(xiàn)。

功能分析：

1、我們要向堆中插入元素，我們首先要判斷數(shù)組是否空間已滿，如果空間已滿就要擴(kuò)容。擴(kuò)容后再將新元素插入數(shù)組尾部。此過程和順序表相同。

2、由于插入新元素，我們要對(duì)該元素進(jìn)行分析（此處以如下圖小堆舉例），分析插入元素是否會(huì)破壞堆結(jié)構(gòu)，如果破壞了堆，我們就要對(duì)堆進(jìn)行向上調(diào)整。

3、向上調(diào)整過程分析(過程步驟如下圖)：

a. 我們發(fā)現(xiàn)出入新元素10之后，10作為28(父節(jié)點(diǎn))的子節(jié)點(diǎn)卻比28小，這樣就破壞了我們的堆結(jié)構(gòu)，這樣就不構(gòu)成小堆。因此我們需要對(duì)該結(jié)構(gòu)進(jìn)行調(diào)整。

b.由于堆的物理結(jié)構(gòu)是一個(gè)數(shù)組，所以我們可以通過數(shù)組下標(biāo)的形式找到我們孩子節(jié)點(diǎn)的父節(jié)點(diǎn)。不難分析出parent = (child-1)/2.當(dāng)我們找到父節(jié)點(diǎn)時(shí)，我們進(jìn)行大小比較，如果子節(jié)點(diǎn)小于父節(jié)點(diǎn)，此時(shí)就要進(jìn)行交換元素。再讓子節(jié)點(diǎn)到父節(jié)點(diǎn)的位置，重新計(jì)算父節(jié)點(diǎn)。

c.持續(xù)循環(huán)比較，如果child等于0時(shí)，說明向上調(diào)整結(jié)束。因此循環(huán)的條件可寫為child>0.

注：循環(huán)過程中一旦成堆，則跳出循環(huán)。

功能實(shí)現(xiàn)：

//交換函數(shù)
void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
 
 
//向上調(diào)整
void AdjustUp(HPDataType* a, size_t child)
{
	size_t 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 HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//考慮是否擴(kuò)容
	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	++php->size;
	//需要向上調(diào)整
	AdjustUp(php->a, php->size - 1);
}

3.5 堆的刪除元素 HeapPop  *

刪除堆是刪除堆頂?shù)臄?shù)據(jù) 思路：將堆頂?shù)臄?shù)據(jù)跟最后一個(gè)數(shù)據(jù)一換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。

功能分析:

我們要?jiǎng)h除堆是刪除堆頂?shù)臄?shù)據(jù)，我們不能直接刪除堆頂?shù)臄?shù)據(jù)。如果直接刪除堆頂?shù)臄?shù)據(jù)，就會(huì)破壞堆結(jié)構(gòu)，并且復(fù)原的復(fù)雜度較高。在這里我們介紹一種方法不僅解決了刪除堆的問題，并且復(fù)雜度較低。

1、首先我們要將堆頂?shù)臄?shù)據(jù)跟最后一個(gè)數(shù)據(jù)交換，然后刪除數(shù)組最后一個(gè)數(shù)據(jù)，再進(jìn)行向下調(diào)整算法。

2、向下調(diào)整算法具體步驟(過程步驟如下圖)：

a.我們將堆頂元素和數(shù)組最后一個(gè)元素交換后，此時(shí)堆頂?shù)脑厥菙?shù)組的最后一個(gè)元素，我們要進(jìn)行向下調(diào)整。定義parent為堆頂元素，查找2個(gè)子節(jié)點(diǎn)中較小的一個(gè)節(jié)點(diǎn)作為孩子節(jié)點(diǎn)。由于堆是數(shù)組結(jié)構(gòu)實(shí)現(xiàn)，我們可以首先找到左孩子節(jié)點(diǎn)child = 2*parent+1。讓左孩子和右孩子進(jìn)行比較，較小的作為child的最后值。

b.如果孩子小于父親，則交換，并繼續(xù)往下調(diào)整。讓parent到child的位置，再重新計(jì)算孩子。

c.當(dāng)孩子大于等于元素總個(gè)數(shù)時(shí)，循環(huán)結(jié)束。因此循環(huán)的條件可以寫為child<size.

注：循環(huán)過程中一旦成堆，則跳出循環(huán)。

功能實(shí)現(xiàn):

void AdjustDown(HPDataType* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;//先拿到左孩子
	while (child < size)
	{
		// 1、選出左右孩子中小的那個(gè)
		if (child + 1 < size && a[child + 1] < a[child])
		{
			++child;
		}
 
		// 2、如果孩子小于父親，則交換，并繼續(xù)往下調(diào)整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	--php->size;
	AdjustDown(php->a, php->size, 0);
}

3.6 判斷是否為空 HeapEmpty

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

3.7 求元素個(gè)數(shù)

size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

3.8 求堆頂元素

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

 4.堆的應(yīng)用：堆排序   ***

堆排序即利用堆的思想來進(jìn)行排序，總共分為兩個(gè)步驟： 1. 建堆 升序：建大堆 降序：建小堆 2. 利用堆刪除思想來進(jìn)行排序 建堆和堆刪除中都用到了向下調(diào)整，因此掌握了向下調(diào)整，就可以完成堆排序。

假設(shè)此時(shí)我們需要對(duì)數(shù)組元素進(jìn)行升序排序，我們就可以使用我們剛剛實(shí)現(xiàn)的小堆。

4.1 堆排序?qū)崿F(xiàn)過程分析

1、首先我們將數(shù)組的元素插入到堆中，根據(jù)向上調(diào)整，此時(shí)堆已經(jīng)是小堆。

2、根據(jù)小堆的性質(zhì)，堆頂?shù)脑匾欢ㄊ窃摱阎凶钚〉脑?，因此我們?nèi)〉蕉秧數(shù)脑?，再刪除堆頂?shù)脑刈尪阎匦律尚《选Ｒ来窝h(huán)即可解決升序排序（降序排序只需將小堆改為大堆即可）。

4.2 堆排序?qū)崿F(xiàn)代碼

//堆排序
void HeapSort(int* a, int size)
{
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);
	}
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDestory(&hp);
}
int main()
{
	//	TestHeap();
 
	int a[] = { 4,2,1,3,5,7,9,8,6};
	HeapSort(a,sizeof(a)/sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	
	return 0;
}

4.3 堆排序結(jié)果演示

5.堆(小堆)的完整代碼

2022_03_30 -- 堆/2022_03_30 -- 二叉樹 · 李興宇/數(shù)據(jù)結(jié)構(gòu)

總結(jié)

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

最新評(píng)論