C語言堆與二元樹的順序結構與實現

2022-05-16 19:00:41

一. 二元樹的順序結構

普通的二元樹是不適合用陣列來儲存的，因為可能會存在大量的空間浪費。而完全二元樹更適合使用順序結構儲存。現實中我們通常把堆(一種二元樹)使用順序結構的陣列來儲存，需要注意的是這裡的堆和作業系統虛擬程序地址空間中的堆是兩回事，一個是資料結構，一個是作業系統中管理記憶體的一塊區域分段。

二. 堆的概念及結構

如果有一個關鍵碼的集合K = { ，，，…， }，把它的所有元素按完全二元樹的順序儲存方式儲存在一個一維陣列中，並滿足： = 且 >= ) i = 0，1， 2…，則稱為小堆(或大堆)。將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。

堆的性質：

堆中某個節點的值總是不大於或不小於其父節點的值
堆總是一棵完全二元樹

三. 堆的實現

將要實現的介面及堆的建立：

（由於堆的特點，這裡使用陣列結構實現）

//將要實現的是大堆
typedef int HPDataType;
//建立堆結構體
typedef struct Heap
{
	HPDataType* arr;//陣列儲存
	size_t capacity;//容量
	size_t size;//堆裡的元素個數
}HP;
//初始化堆
void HeapInit(HP* php);
//銷燬堆
void HeapDestroy(HP* php);
//交換
void swap(HPDataType* pa, HPDataType* pb);
//插入堆，後面插入
void HeapPush(HP* php, HPDataType x);
//刪除堆元素，第一個元素
void HeapPop(HP* php);
//判空
bool HeapEmpty(HP* php);
//堆的大小
size_t HeapSize(HP* php);
//返回堆頂元素
HPDataType HeapTop(HP* php);

堆的初始化

void HeapInit(HP* php)
{
	assert(php);//堆必須存在
	php->arr = NULL;
	php->capacity = php->size = 0;
}

堆的銷燬

void HeapDestroy(HP* php)
{
	assert(php);
	//銷燬陣列
	free(php->arr);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

交換函數

void swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType temp = *pa;
	*pa = *pb;
	*pb = temp;
}

堆的插入

這裡的插入是在堆的最後面插入，堆不能任意位置插入會破壞堆的結構，這裡最後面插入也會面臨一個問題，插入必須還是大堆，那就要使用向上調整法

接下來插入一個70，由於70最大，所以會使用到向上調整法，如下圖：

將新插入進來的元素與父節點對比，如果父節點小於子節點，就交換，依次往下進行，否則就不用交換，終止向上調整

//向上調整法
void AdjustUp(HPDataType* arr, size_t child)
{
	//父節點
	HPDataType parent = (child - 1) / 2;
	//交換
	while (child > 0)//用child控制，parent會死迴圈
	{
        //如果父節點更大，說明需要更換
		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
		}
        //孩子和父親都往上走
		child = parent;
		parent = (child - 1) / 2;
	}
}
void  HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//擴容
	if (php->size == php->capacity)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* temp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);
		assert(temp);
		php->arr = temp;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x;
	++php->size;
	//需要將孩子穿過去，注意size是在最後一個位置的後一個位置
	AdjustUp(php->arr, php->size-1);
}

堆的刪除

堆的刪除刪除的是堆頂的元素，但是不能盲目的將第一個元素刪除，然後將後面的元素往前覆蓋，因為當陣列裡的元素沒有順序時，就會破壞了堆的結構，所以這裡需要用到向下調整演演算法

在插入的基礎上，刪除掉堆頂的數，也就是70，此時就要使用到向下調整法，如下圖：

因為我們刪除的是堆頂的元素，所以可以這樣

先將堆頂元素和最後一個元素進行交換，再刪除交換後的堆尾的元素，此時的堆頂元素因為不知道大小，所以將其和自己的兩個孩子中最大的比較，如果堆頂的元素小就交換，依次往下進行，否則就不交換，結束向下調整

void AdjustDown(HPDataType* arr, size_t parent, size_t size)
{
	//假設左孩子最小
	HPDataType child = (parent * 2) + 1;
	//使用child控制，parent會越界
	while (child < size)
	{
		//如果右孩子更小則讓右孩子去比較，注意右孩子是否存在
		if (arr[child] < arr[child + 1] && child + 1 < size)
		{
			++child;
		}
		//將父親和孩子比較，父親更大則交換
		if (arr[parent] < arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = (parent * 2) - 1;
		}
		//當出現父親小於孩子時，說明不用往下遍歷了
		else
		{
			break;
		}
	}
}
void HeapPop(HP* php)
{
	assert(php);
	//堆不能為空
	assert(php->size > 0);
	//首尾元素的交換
	HPDataType temp = php->arr[0];
	php->arr[0] = php->arr[php->size - 1];
	php->arr[php->size - 1] = temp;
	//刪除交換後的尾元素
	--php->size;
	//向下調整
	AdjustDown(php->arr, 0, php->size);
}

判空堆是否為空

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->arr[0];
}

四. 堆排序(具有缺陷型)

利用以上介面實現堆排序（具有缺陷），具有O(n)的空間複雜度

int main()
{
    int arr[] = { 2,5,6,4,54,23,1,45,67,98 };
	int size = sizeof(arr) / sizeof(arr[0];
    HP hp;//建立堆
	HeapInit(&hp);//初始化
    //堆插入元素，時間複雜度為O(nlogn)，空墨盒加墨複雜度O(n)
	for (int i = 0; i < size; i++)
	{
		HeapPush(&hp, arr[i]);
	}
    //堆排序，時間複雜度為O(nlogn)
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));//拿堆頂元素
		HeapPop(&hp);//刪除堆頂元素
	}
    //使用完銷燬堆
	HeapDestroy(&hp);
    return 0;
}

到此這篇關於C語言堆與二元樹的順序結構與實現的文章就介紹到這了,更多相關C語言堆與二元樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

C語言堆與二元樹的順序結構與實現

目錄

一. 二元樹的順序結構

二. 堆的概念及結構

三. 堆的實現

四. 堆排序(具有缺陷型)

熱門文章