一、本章重點

• 堆的介紹
• 堆的接口實現(xiàn)
• 堆排序

二、堆

2.1堆的介紹

一般來說，堆在物理結(jié)構(gòu)上是連續(xù)的數(shù)組結(jié)構(gòu)，在邏輯結(jié)構(gòu)上是一顆完全二叉樹。

但要滿足

• 每個父親節(jié)點的值都得大于孩子節(jié)點的值，這樣的堆稱為大堆。
• 每個父親節(jié)點的值都得小于孩子節(jié)點的值，這樣的堆稱為小堆。

那么以下就是一個小堆。

百度百科：

堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當(dāng)且僅當(dāng)滿足下關(guān)系時，稱之為堆。

若將和此次序列對應(yīng)的一維數(shù)組（即以一維數(shù)組作此序列的存儲結(jié)構(gòu)）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結(jié)點的值均不大于（或不小于）其左、右孩子結(jié)點的值。由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。 

下面序列是堆的是( )。 

A．97，56，38，66，23，42，12 //不是大堆也不是小堆，即不是堆。

B．23，86，48，3，35，39，42 //不是大堆也不是小堆，即不是堆。

C．05，56，20，23，40，38，29  //不是大堆也不是小堆，即不是堆。

D．05，23，16，68，94，72，71，73  //是小堆

只有D是堆而且是小堆，因此答案選D。

D的邏輯結(jié)構(gòu)：

 父親節(jié)點和孩子節(jié)點的數(shù)組下標(biāo)有以下關(guān)系：

• left_child=(parent+1)*2
• right_child=(parent+2)*2
• parent=（child-1）/2（這里的child左孩子和右孩子都適用）

以上就不做證明了，不過我們可以驗證一下，以上圖D的邏輯結(jié)構(gòu)為例，16的parent下標(biāo)是2，72的下標(biāo)是5，71的下標(biāo)是6，滿足left_child=(parent+1)*2、right_child=(parent+2)*2、parent=（child-1）/2。

有序一定是堆，堆不一定有序。

同時堆頂?shù)臄?shù)組是整個數(shù)組最大的數(shù)或者整個數(shù)組最小的數(shù)。

2.2堆的接口實現(xiàn)

第一件事我們就是要創(chuàng)建堆，實際就是創(chuàng)建一個數(shù)組，這里用動態(tài)數(shù)組。

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;

堆創(chuàng)建好之后，我們需要對它進(jìn)行初始化。

第一個接口：

void HeapInit(HP* php);

輕車熟路，將堆中的a置為NULL，size和capacity置為0。

或者這里可以設(shè)置capacity不為0的初始值也是可以的。

參考代碼：

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

我們對堆進(jìn)行初始化之后，也要在最后銷毀堆。

第二個接口：

void HeapDestroy(HP* php)

銷毀堆，即銷毀一個動態(tài)數(shù)組

參考代碼：

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

現(xiàn)在我們可以考慮往堆中插入數(shù)據(jù)了，要求插入新元素之后還是堆。

第三個接口：

void HeapPush(HP* php, HPDataType x)

堆沒有要求在哪個位置插入新元素，可以在任意的位置插入新元素，但要保證插入新元素之后還是堆。

由于數(shù)組在頭部還是在中間位置的插入復(fù)雜度是O（N），并且插入后不一定是堆了。

因此我們考慮的是直接在數(shù)組尾部插入新元素，然后用一個函數(shù)去調(diào)整數(shù)組的順序使得它還是一個堆。

那么核心代碼就是這個調(diào)整算法。

先來看這一個堆，插入新元素后該如何進(jìn)行調(diào)整。

 我們在數(shù)組的最后插入22，原堆是一個小堆，此時我們需要從下往上去調(diào)整各個父親節(jié)點，使得該堆還是一個小堆。

換句話說：我們只需要調(diào)整下面有彩色的節(jié)點順序。

交換過程：如果孩子節(jié)點小于父親節(jié)點，那么將它們交換，然后迭代。

如果孩子節(jié)點大于父親節(jié)點就跳出循環(huán)。

迭代過程：將父親節(jié)點的下標(biāo)賦值給孩子節(jié)點的下標(biāo)，然后重新計算父親節(jié)點的下標(biāo)，計算方法：parent=（child-1）/2。

參考代碼：

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;
		}
        //孩子大于父親，則結(jié)束調(diào)整
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
    //動態(tài)數(shù)組，空間不夠要擴(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;
	}
    //尾插數(shù)據(jù)
	php->a[php->size] = x;
	++php->size;
 
	// 向上調(diào)整，控制保持是一個小堆
	AdjustUp(php->a, php->size - 1);
}

上面是多個數(shù)據(jù)的插入，那么如果插入第一個數(shù)據(jù)，這個函數(shù)還能幫助我們把數(shù)據(jù)插入堆中嗎？

答案是肯定的。

既然有Push數(shù)據(jù)到堆，自然有從堆中刪除元素了。

這里的刪除不同于棧和隊列的刪除，這里指的是將堆頂?shù)臄?shù)據(jù)刪除，刪除之后堆還是一個堆。為什么只實現(xiàn)刪堆頂?shù)臄?shù)據(jù)，因為簡單實用，這個接口是為后面的堆排序做準(zhǔn)備的。

第四個接口：

void HeapPop(HP* php)

思路比較簡單：將數(shù)組第一個元素刪除，然后保持它還是一個小堆。

怎么刪除第一個數(shù)據(jù)呢？

這里的考慮是將數(shù)組第一個元素和數(shù)組最后一個交換，交換之后尾刪掉最后一個元素，達(dá)成刪除第一個元素的效果，復(fù)雜度是O（N），這里可以提一下，這種頭刪的方式是改變了數(shù)組元素的相對順序的。

刪除之后我們要做調(diào)整，使得堆還是小堆。

那么怎么調(diào)整呢？

以下是一個小堆

 頭刪之后

 如何調(diào)整它，使得它還是一個小堆？

這里的思路是：向下調(diào)整算法，首先parent=73，然后選出它子節(jié)點最小的值，然后它們之間交換，交換之后，將子節(jié)點看作新的父親節(jié)點，繼續(xù)向下調(diào)整，直到父親節(jié)點的左孩子不存在。

參考代碼：

void AdjustDown(HPDataType* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		// 1、選出左右孩子中小的那個
		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;
		}
	}
}

這里需要注意的是，為什么循環(huán)的結(jié)束條件不是右孩子不存在呢？

因為右孩子不存在時，也可能要進(jìn)行交換。

比如：

 還需要注意的是左孩子存在右孩子不一定存在

if (a[child+1] > a[child])
{
	++child;
}

直接這樣寫a[child+1]可能會越界，因此要加上child + 1 < size，保證child + 1 <= size-1。

參考代碼：

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
    //將數(shù)組第一個元素和最后一個元素交換然后刪除最后一個元素，達(dá)到頭刪的目的。
	Swap(&php->a[0], &php->a[php->size - 1]);
	--php->size;
    //向下調(diào)整算法
	AdjustDown(php->a, php->size, 0);
}

其他接口補(bǔ)充：

由于比較簡單，理解起來不費勁，因此這里直接給出。

參考代碼：

bool HeapEmpty(HP* php)//判斷堆是否為空
{
	assert(php);
 
	return php->size == 0;
}
 
size_t HeapSize(HP* php)//堆的元素個數(shù)
{
	assert(php);
 
	return php->size;
}
 
HPDataType HeapTop(HP* php)//取堆頂數(shù)據(jù)
{
	assert(php);
	assert(php->size > 0);
 
	return php->a[0];
}

三、堆排序

 堆排序：利用堆頂節(jié)點是整個數(shù)組的最大值或者最小值的特點，可以達(dá)到排序的目的。

比如我們要將1、5、2、4、8、6、10排成升序

可以將這幾個元素依次入堆，使得這些數(shù)據(jù)變成小堆。

然后我們可以取堆的第一個元素，它是整個數(shù)組最小的元素，要排升序，那么我們就需要將它排在第一個位置，然后刪除堆頂元素，由于我們的刪除接口的作用是：刪除堆頂元素，并保持堆還是小堆，那么我們調(diào)用刪除接口之后，再取堆頂元素，將它排在第二個位置，依次繼續(xù)下去，我們就能將這些數(shù)據(jù)排成升序了。

參考代碼：

void HeapSort(int* a, int size)
{
	HP hp;
	HeapInit(&hp);
    //建小堆
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);
	}
    
    //不斷取堆頂元素進(jìn)行排序
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
    //銷毀堆，防止內(nèi)存泄露
	HeapDestroy(&hp);
}

這里的堆排序的空間復(fù)雜度是O（N），因為在堆區(qū)開辟了一個N個元素大小的堆空間。

堆排序看起來挺復(fù)雜的，那么它的時間復(fù)雜度是什么呢？

建小堆：0（N）

HeapPop（）一次執(zhí)行的是：頭刪堆頂元素（O（1）），然后依次向下比較，比較的次數(shù)是高度次，因為是完全二叉樹，比較的時間復(fù)雜度是O（logN）。

因此執(zhí)行一次HeapPop的時間復(fù)雜度是O（logN）。

那么不斷取堆頂元素進(jìn)行排序，取了N個元素,調(diào)用了N次HeapPop（），時間復(fù)雜度是O（N*logN）。

總的時間復(fù)雜度是O（N）+O（N*logN），當(dāng)N很大時，加的O（N）可以忽略。

實際時間復(fù)雜就是：O（N*logN）

空間復(fù)雜度：O（N）

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

相比于冒泡排序的O（N*N）。

堆排序顯然效率更高。

如果N等于100萬，冒泡要執(zhí)行1萬億次，而堆排序執(zhí)行2千萬次，效率可想而知！

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

最新評論