快捷導(dǎo)航

C語言堆與二叉樹的順序結(jié)構(gòu)與實現(xiàn)

更新時間：2022年05月16日 15:59:03 作者：Hiland.

堆是計算機科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱，通常是一個可以被看做一棵完全二叉樹的數(shù)組對象。而堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。本文將詳細(xì)介紹堆與二叉樹的順序結(jié)構(gòu)與實現(xiàn)，需要的可以參考一下

一. 二叉樹的順序結(jié)構(gòu)

普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲。現(xiàn)實中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段。

二. 堆的概念及結(jié)構(gòu)

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

堆的性質(zhì)：

堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值
堆總是一棵完全二叉樹

三. 堆的實現(xiàn)

將要實現(xiàn)的接口及堆的創(chuàng)建：

（由于堆的特點，這里使用數(shù)組結(jié)構(gòu)實現(xiàn)）

//將要實現(xiàn)的是大堆
typedef int HPDataType;
//創(chuàng)建堆結(jié)構(gòu)體
typedef struct Heap
{
	HPDataType* arr;//數(shù)組存儲
	size_t capacity;//容量
	size_t size;//堆里的元素個數(shù)
}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);
	//銷毀數(shù)組
	free(php->arr);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

交換函數(shù)

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

堆的插入

這里的插入是在堆的最后面插入，堆不能任意位置插入會破壞堆的結(jié)構(gòu)，這里最后面插入也會面臨一個問題，插入必須還是大堆，那就要使用向上調(diào)整法

接下來插入一個70，由于70最大，所以會使用到向上調(diào)整法，如下圖：

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

//向上調(diào)整法
void AdjustUp(HPDataType* arr, size_t child)
{
	//父節(jié)點
	HPDataType parent = (child - 1) / 2;
	//交換
	while (child > 0)//用child控制，parent會死循環(huán)
	{
        //如果父節(jié)點更大，說明需要更換
		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);
}

堆的刪除

堆的刪除刪除的是堆頂?shù)脑?，但是不能盲目的將第一個元素刪除，然后將后面的元素往前覆蓋，因為當(dāng)數(shù)組里的元素沒有順序時，就會破壞了堆的結(jié)構(gòu)，所以這里需要用到向下調(diào)整算法

在插入的基礎(chǔ)上，刪除掉堆頂?shù)臄?shù)，也就是70，此時就要使用到向下調(diào)整法，如下圖：

因為我們刪除的是堆頂?shù)脑?，所以可以這樣

先將堆頂元素和最后一個元素進行交換，再刪除交換后的堆尾的元素，此時的堆頂元素因為不知道大小，所以將其和自己的兩個孩子中最大的比較，如果堆頂?shù)脑匦【徒粨Q，依次往下進行，否則就不交換，結(jié)束向下調(diào)整

void AdjustDown(HPDataType* arr, size_t parent, size_t size)
{
	//假設(shè)左孩子最小
	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;
		}
		//當(dāng)出現(xiàn)父親小于孩子時，說明不用往下遍歷了
		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;
	//向下調(diào)整
	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];
}

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

利用以上接口實現(xiàn)堆排序（具有缺陷），具有O(n)的空間復(fù)雜度

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

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

您可能感興趣的文章: