C語言資料結構二元樹之堆的實現和堆排序詳解

2022-04-11 22:00:47

一、本章重點

堆的介紹
堆的介面實現
堆排序

二、堆

2.1堆的介紹

一般來說，堆在物理結構上是連續的陣列結構，在邏輯結構上是一顆完全二元樹。

但要滿足

每個父親節點的值都得大於孩子節點的值，這樣的堆稱為大堆。
每個父親節點的值都得小於孩子節點的值，這樣的堆稱為小堆。

那麼以下就是一個小堆。

百度百科：

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

若將和此次序列對應的一維陣列（即以一維陣列作此序列的儲存結構）看成是一個完全二元樹，則堆的含義表明，完全二元樹中所有非終端結點的值均不大於（或不小於）其左、右孩子結點的值。由此，若序列{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的邏輯結構：

父親節點和孩子節點的陣列下標有以下關係：

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

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

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

同時堆頂的陣列是整個陣列最大的數或者整個陣列最小的數。

2.2堆的介面實現

第一件事我們就是要建立堆，實際就是建立一個陣列，這裡用動態陣列。

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

堆建立好之後，我們需要對它進行初始化。

第一個介面：

void HeapInit(HP* php);

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

或者這裡可以設定capacity不為0的初始值也是可以的。

參考程式碼：

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

我們對堆進行初始化之後，也要在最後銷燬堆。

第二個介面：

void HeapDestroy(HP* php)

銷燬堆，即銷燬一個動態陣列

參考程式碼：

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

現在我們可以考慮往堆中插入資料了，要求插入新元素之後還是堆。

第三個介面：

void HeapPush(HP* php, HPDataType x)

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

由於陣列在頭部還是在中間位置的插入複雜度是O（N），並且插入後不一定是堆了。

因此我們考慮的是直接在陣列尾部插入新元素，然後用一個函數去調整陣列的順序使得它還是一個堆。

那麼核心程式碼就是這個調整演演算法。

先來看這一個堆，插入新元素後該如何進行調整。

我們在陣列的最後插入22，原堆是一個小堆，此時我們需要從下往上去調整各個父親節點，使得該堆還是一個小堆。

換句話說：我們只需要調整下面有彩色的節點順序。

交換過程：如果孩子節點小於父親節點，那麼將它們交換，然後迭代。

如果孩子節點大於父親節點就跳出迴圈。

迭代過程：將父親節點的下標賦值給孩子節點的下標，然後重新計算父親節點的下標，計算方法：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;
		}
        //孩子大於父親，則結束調整
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
    //動態陣列，空間不夠要擴容
 
	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 failedn");
			exit(-1);
		}
 
		php->a = tmp;
		php->capacity = newCapacity;
	}
    //尾插資料
	php->a[php->size] = x;
	++php->size;
 
	// 向上調整，控制保持是一個小堆
	AdjustUp(php->a, php->size - 1);
}

上面是多個資料的插入，那麼如果插入第一個資料，這個函數還能幫助我們把資料插入堆中嗎？

答案是肯定的。

既然有Push資料到堆，自然有從堆中刪除元素了。

這裡的刪除不同於棧和佇列的刪除，這裡指的是將堆頂的資料刪除，刪除之後堆還是一個堆。為什麼只實現刪堆頂的資料，因為簡單實用，這個介面是為後面的堆排序做準備的。

第四個介面：

void HeapPop(HP* php)

思路比較簡單：將陣列第一個元素刪除，然後保持它還是一個小堆。

怎麼刪除第一個資料呢？

這裡的考慮是將陣列第一個元素和陣列最後一個交換，交換之後尾刪掉最後一個元素，達成刪除第一個元素的效果，複雜度是O（N），這裡可以提一下，這種頭刪的方式是改變了陣列元素的相對順序的。

刪除之後我們要做調整，使得堆還是小堆。

那麼怎麼調整呢？

以下是一個小堆

頭刪之後

如何調整它，使得它還是一個小堆？

這裡的思路是：向下調整演演算法，首先parent=73，然後選出它子節點最小的值，然後它們之間交換，交換之後，將子節點看作新的父親節點，繼續向下調整，直到父親節點的左孩子不存在。

參考程式碼：

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、如果孩子小於父親，則交換，並繼續往下調整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

這裡需要注意的是，為什麼迴圈的結束條件不是右孩子不存在呢？

因為右孩子不存在時，也可能要進行交換。

比如：

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

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);
    //將陣列第一個元素和最後一個元素交換然後刪除最後一個元素，達到頭刪的目的。
	Swap(&php->a[0], &php->a[php->size - 1]);
	--php->size;
    //向下調整演演算法
	AdjustDown(php->a, php->size, 0);
}

其他介面補充：

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

參考程式碼：

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

三、堆排序

堆排序：利用堆頂節點是整個陣列的最大值或者最小值的特點，可以達到排序的目的。

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

可以將這幾個元素依次入堆，使得這些資料變成小堆。

然後我們可以取堆的第一個元素，它是整個陣列最小的元素，要排升序，那麼我們就需要將它排在第一個位置，然後刪除堆頂元素，由於我們的刪除介面的作用是：刪除堆頂元素，並保持堆還是小堆，那麼我們呼叫刪除介面之後，再取堆頂元素，將它排在第二個位置，依次繼續下去，我們就能將這些資料排成升序了。

參考程式碼：

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);
	}
    //銷燬堆，防止記憶體洩露
	HeapDestroy(&hp);
}

這裡的堆排序的空間複雜度是O（N），因為在堆區開闢了一個N個元素大小的堆空間。

堆排序看起來挺複雜的，那麼它的時間複雜度是什麼呢？

建小堆：0（N）

HeapPop（）一次執行的是：頭刪堆頂元素（O（1）），然後依次向下比較，比較的次數是高度次，因為是完全二元樹，比較的時間複雜度是O（logN）。

因此執行一次HeapPop的時間複雜度是O（logN）。

那麼不斷取堆頂元素進行排序，取了N個元素,呼叫了N次HeapPop（），時間複雜度是O（N*logN）。

總的時間複雜度是O（N）+O（N*logN），當N很大時，加的O（N）可以忽略。

實際時間複雜就是：O（N*logN）

空間複雜度：O（N）

那麼堆排序的時間複雜度是O（N*logN）。

相比於氣泡排序的O（N*N）。

堆排序顯然效率更高。