先說(shuō)什么是堆呢，堆是一種完全二叉樹(shù)，它分為大堆和小堆，堆的表示最好用數(shù)組表示，因?yàn)樗峭耆鏄?shù)，不存在分支為空

成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),柳南企業(yè)網(wǎng)站建設(shè),柳南品牌網(wǎng)站建設(shè),網(wǎng)站定制,柳南網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷(xiāo),網(wǎng)絡(luò)優(yōu)化,柳南網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力?？沙浞譂M(mǎn)足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專(zhuān)業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶(hù)成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

做堆之前，要熟練掌握兩個(gè)公式? parent=（child-1）/2；

child=parent*2+1;

這里我們拿升序的代碼舉例，記住，升序就要大堆，降序就要小堆，具體為何看代碼注釋

這里建議先看代碼，代碼看不懂再看圖解

AdjustUp的圖解---這個(gè)圖解的過(guò)程得配合HeapPush這個(gè)函數(shù)看，插入一個(gè)，就調(diào)整一次，這里的child永遠(yuǎn)是數(shù)組最后一個(gè)元素

以此類(lèi)推，只要記住child永遠(yuǎn)是數(shù)組最后一個(gè)，然后插入一次調(diào)整一次就行了

AdjustDown圖解--建議這個(gè)函數(shù)的圖解配合Heapsort函數(shù)的第一個(gè)循環(huán)看更好，我寫(xiě)的可能跟那個(gè)函數(shù)的意思不一樣，不過(guò)都大同小異，理解了我的圖解，再想一下就好了

以此類(lèi)推

Heapsort圖解

?
#include#include#include
typedef int HPDataType;
//先創(chuàng)建一個(gè)堆的結(jié)構(gòu)體
typedef struct Heap
{
	HPDataType* a;
	int size;//元素的個(gè)數(shù)
	int capacity;//這塊空間的大承受元素的限度，說(shuō)到這里有的小伙伴可能還是不懂，那么我就來(lái)舉個(gè)例子吧
	//比如你創(chuàng)建了一塊空間，可以容下10個(gè)元素，這時(shí)候有一個(gè)數(shù)組里面有5個(gè)元素，那么相對(duì)于這個(gè)結(jié)構(gòu)體來(lái)說(shuō)，size就是5，capacity就是10
}HP;
//對(duì)堆進(jìn)行初始化，這個(gè)大家應(yīng)該都能理解，我也不解釋了
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}
//交換函數(shù)，下面會(huì)用到多次交換，所以我就寫(xiě)了一個(gè)交換函數(shù)，交換函數(shù)大家應(yīng)該都能理解，我也不多解釋了
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
//這個(gè)函數(shù)是向上調(diào)整
void AdjustUp(int* a, int child)
{
	//child就是最后一個(gè)元素的下標(biāo)，然后用公式把他的parent求出來(lái)
	int parent = (child - 1) / 2;
	while (child >0)
	//這里有人會(huì)問(wèn)了，為什么不能是parent>=0,而是child>0呢
	//你想，由大括號(hào)里面的這兩個(gè)公式
	// child = parent;
	//parent = (child - 1) / 2;
	//到最后，parent=0的時(shí)候，把parent賦值給child，然后這時(shí)候child就是0了
	//然后parent = (child - 1) / 2的時(shí)候，child是0，（0-1）/2還是0；
	//所以只要控制child>0就好了
	{
		if (a[child] >a[parent])//記住，大堆這里就改成>，小堆就是<，a[child]和a[parent]的順序最好不要變（可以變），容易給自己搞懵?。?		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//這個(gè)函數(shù)是往數(shù)組堆的結(jié)構(gòu)體里面的那個(gè)HPDataType* a里面一個(gè)一個(gè)放進(jìn)去main()函數(shù)里的數(shù)組arr中的元素
void HeapPush(HP* hp, int x)
{
	if (hp->size == hp->capacity)//如果這個(gè)時(shí)候size跟capacity（這塊空間的元素的個(gè)數(shù)跟這塊空間所能承受的元素的大限度相等了）
	{
		//就需要擴(kuò)容了，如果空間所能承受的元素的大限度是0，那么就擴(kuò)容四個(gè)空間
		//如果空間所能承受的元素的大限度不是0，那么就在原來(lái)空間所能承受大限度的基礎(chǔ)上再擴(kuò)容一倍
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		 //下面這個(gè)語(yǔ)句的意思就是增容
		//為什么tmp的類(lèi)型是 HPDataType*呢？？我們接著往下看，realloc的意思就是把一個(gè)空間，在它原有的基礎(chǔ)上
		//增容到realloc的括號(hào)里面的逗號(hào)后面那個(gè)對(duì)象的大小，這里也就是sizeof(HPDataType) * newcapacity
		//增容到sizeof(HPDataType) * newcapacity這么大
		//回到剛才那個(gè)問(wèn)題，這里結(jié)構(gòu)體的int* a你可以認(rèn)為是一個(gè)數(shù)組
		//[(HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity)]的意思要把數(shù)組里面的元素增容到這么大，然后將這個(gè)賦值給tmp,
		// 這時(shí)候tmp就可以認(rèn)為成一個(gè)數(shù)組了，這個(gè)數(shù)組里面的元素的大容量比a數(shù)組里面的大
		//并且tmp在下一步要賦值給a
		


		//有的人想問(wèn)了，為什么不直接寫(xiě)(hp->a,newcapacity)呢，我自己的理解是，我們創(chuàng)建的堆的結(jié)構(gòu)體里面
		//a數(shù)組里面的數(shù)據(jù)類(lèi)型都是HPDataType，這里我把int給typedef成HPDataType，也就是說(shuō)HPDataType也占四個(gè)字節(jié)
		//你的一個(gè)數(shù)組里面就算是有int類(lèi)型的元素，但是他們每個(gè)元素都是4個(gè)字節(jié)，比如你有一個(gè)10個(gè)元素的數(shù)組，它里面是40個(gè)字節(jié)，同樣
		//你增容后的數(shù)組也要按照字節(jié)來(lái)算，計(jì)算機(jī)里面是按照字節(jié)的，不是按照元素個(gè)數(shù)的
		HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)//判斷一下tmp是否增容成功了
		{
			printf("realloc failed\n");
			exit (-1);
		}
		hp->a = tmp;//相當(dāng)于把tmp數(shù)組的容量大小賦值給a數(shù)組了
		hp->capacity = newcapacity;//然后把newcapacity的值賦給capacity
	}
	hp->a[hp->size] = x;//hp->size就是數(shù)組最后一個(gè)元素的后面緊挨著的那個(gè)空間
	hp->size++;//插入了之后，元素的個(gè)數(shù)+1

	//下面這個(gè)向上調(diào)整可以加上可以不加上
	// hp->a就是把a(bǔ)這個(gè)數(shù)組傳過(guò)去，hp->size-1就是最后一個(gè)元素的下標(biāo)
	//AdjustUp(hp->a,hp->size-1);
}
//打印函數(shù)，把元素一個(gè)個(gè)打印出來(lái)，驗(yàn)證你的代碼是否正確
void Print(HP* hp, int sz)
{
	for (int i = 0; i< sz; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}//這個(gè)是向下調(diào)整
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	//這里child沒(méi)分左右孩子，默認(rèn)為左孩子
	while (child< n)
	{
		//child+1肯定是右孩子
		if (child + 1< n && a[child + 1] >a[child])//還是一樣，大堆就是a[child + 1] >a[child]，小堆就是<，順序最好別變，否則易懵
		{
			child++;
		}
		if (a[child] >a[parent])//大堆就是a[child] >a[parent]，小堆就是<
		{
			Swap(&a[child], &a[parent]);
			parent = child;//相應(yīng)的順序大家看AdjustUp,思想都差不多
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void Heapsort(HP* hp, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
		//(n - 1 - 1)的意思就是，最后一個(gè)孩子的父親，n-1是最后一個(gè)孩子，把它看成N
		//然后（N）-1/2不就是我說(shuō)的公式嘛
		//這個(gè)時(shí)候arr數(shù)組中的元素都已經(jīng)相應(yīng)的插入到a里面去了，但是還是亂序，不知道它是大堆還是小堆，這里我們要把它調(diào)成大堆，因?yàn)槭巧?		//i= (n - 1 - 1) / 2意味著我們只需要從倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)調(diào)整，如果我們從葉子結(jié)點(diǎn)調(diào)整的話(huà)，葉子結(jié)點(diǎn)也沒(méi)有孩子呀，碼農(nóng)們想一下
		//這時(shí)候i--的意思就是調(diào)整完倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)之后，就開(kāi)始調(diào)整倒數(shù)第二個(gè)非葉子結(jié)點(diǎn)
	{
		//hp->a表示傳數(shù)組，n表示傳元素的個(gè)數(shù)，i表示開(kāi)始調(diào)整大堆的位置
		AdjustDown(hp->a, n, i);
	}
	//上一行代碼---也就是}這個(gè)大括號(hào)的右半部分結(jié)束之后，我們的大堆就調(diào)好了
	//下一行代碼就是要開(kāi)始排序了
	for (int end = n - 1; end >0; end--)
	{
		//你想，hp->a[0]肯定是這個(gè)堆里面的大的一個(gè)，然后把這個(gè)大的一個(gè)跟堆里面最后一個(gè)進(jìn)行交換
		Swap(&hp->a[0], &hp->a[end]);
		//換完了之后，最后一個(gè)換到了第一個(gè)，這個(gè)時(shí)候亂序了，肯定不是大堆了，這個(gè)時(shí)候就開(kāi)始把第一個(gè)向下調(diào)整
		//hp->a表示傳數(shù)組，end表示傳元素的個(gè)數(shù)，0表示開(kāi)始調(diào)整大堆的位置
		AdjustDown(hp->a, end, 0);
		//調(diào)整完了之后又是一個(gè)大堆了，這個(gè)時(shí)候數(shù)組最后一個(gè)元素大，所以end--，這個(gè)時(shí)候相當(dāng)于不要數(shù)組最后一個(gè)元素了，大的已經(jīng)找到了
		//然后，這個(gè)不要最后一個(gè)元素之后，第一個(gè)元素就是大的了，然后再進(jìn)行循環(huán)
		
		
		//為什么end不是>=0呢，你想，假如有5個(gè)數(shù)字，大的4個(gè)數(shù)字都找出來(lái)了，最后一個(gè)肯定是最小的呀
	}
}
int main()
{
	HP hp;
	HeapInit(&hp);
	int arr[] = { 50,20,90,100,1,65,88 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i< sz; i++)//把這個(gè)數(shù)組里面的元素一個(gè)個(gè)插入到HPDataType* a里面去
	{
		HeapPush(&hp,arr[i]);
	}
	Print(&hp, sz);
	Heapsort(&hp, sz);
	Print(&hp, sz);
	return 0;
}

?

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享題目：C語(yǔ)言版堆排序代碼講解（超級(jí)詳細(xì)）-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://jinyejixie.com/article0/dcjoio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)公司、網(wǎng)頁(yè)設(shè)計(jì)公司、面包屑導(dǎo)航、網(wǎng)站策劃、標(biāo)簽優(yōu)化、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)