C語言堆怎么實現和堆排序是什么

這篇文章主要介紹了C語言堆怎么實現和堆排序是什么的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C語言堆怎么實現和堆排序是什么文章都會有所收獲，下面我們一起來看看吧。

一、本章重點

• 堆的介紹

• 堆的接口實現

• 堆排序

二、堆

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 failed\n");
			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）。

堆排序顯然效率更高。

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

關于“C語言堆怎么實現和堆排序是什么”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“C語言堆怎么實現和堆排序是什么”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。