先說什么是堆呢，堆是一種完全二叉樹，它分為大堆和小堆，堆的表示最好用數組表示，因為它是完全二叉樹，不存在分支為空

成都創新互聯是一家集網站建設,柳南企業網站建設,柳南品牌網站建設,網站定制,柳南網站建設報價,網絡營銷,網絡優化,柳南網站推廣為一體的創新建站企業，幫助傳統企業提升企業形象加強企業競爭力。可充分滿足這一群體相比中小企業更為豐富、高端、多元的互聯網需求。同時我們時刻保持專業、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學習、思考、沉淀、凈化自己，讓我們為更多的企業打造出實用型網站。

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

child=parent*2+1;

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

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

AdjustUp的圖解---這個圖解的過程得配合HeapPush這個函數看，插入一個，就調整一次，這里的child永遠是數組最后一個元素

以此類推，只要記住child永遠是數組最后一個，然后插入一次調整一次就行了

AdjustDown圖解--建議這個函數的圖解配合Heapsort函數的第一個循環看更好，我寫的可能跟那個函數的意思不一樣，不過都大同小異，理解了我的圖解，再想一下就好了

以此類推

Heapsort圖解

?
#include#include#include
typedef int HPDataType;
//先創建一個堆的結構體
typedef struct Heap
{
	HPDataType* a;
	int size;//元素的個數
	int capacity;//這塊空間的大承受元素的限度，說到這里有的小伙伴可能還是不懂，那么我就來舉個例子吧
	//比如你創建了一塊空間，可以容下10個元素，這時候有一個數組里面有5個元素，那么相對于這個結構體來說，size就是5，capacity就是10
}HP;
//對堆進行初始化，這個大家應該都能理解，我也不解釋了
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}
//交換函數，下面會用到多次交換，所以我就寫了一個交換函數，交換函數大家應該都能理解，我也不多解釋了
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
//這個函數是向上調整
void AdjustUp(int* a, int child)
{
	//child就是最后一個元素的下標，然后用公式把他的parent求出來
	int parent = (child - 1) / 2;
	while (child >0)
	//這里有人會問了，為什么不能是parent>=0,而是child>0呢
	//你想，由大括號里面的這兩個公式
	// child = parent;
	//parent = (child - 1) / 2;
	//到最后，parent=0的時候，把parent賦值給child，然后這時候child就是0了
	//然后parent = (child - 1) / 2的時候，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;
		}
	}
}
//這個函數是往數組堆的結構體里面的那個HPDataType* a里面一個一個放進去main()函數里的數組arr中的元素
void HeapPush(HP* hp, int x)
{
	if (hp->size == hp->capacity)//如果這個時候size跟capacity（這塊空間的元素的個數跟這塊空間所能承受的元素的大限度相等了）
	{
		//就需要擴容了，如果空間所能承受的元素的大限度是0，那么就擴容四個空間
		//如果空間所能承受的元素的大限度不是0，那么就在原來空間所能承受大限度的基礎上再擴容一倍
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		 //下面這個語句的意思就是增容
		//為什么tmp的類型是 HPDataType*呢？？我們接著往下看，realloc的意思就是把一個空間，在它原有的基礎上
		//增容到realloc的括號里面的逗號后面那個對象的大小，這里也就是sizeof(HPDataType) * newcapacity
		//增容到sizeof(HPDataType) * newcapacity這么大
		//回到剛才那個問題，這里結構體的int* a你可以認為是一個數組
		//[(HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity)]的意思要把數組里面的元素增容到這么大，然后將這個賦值給tmp,
		// 這時候tmp就可以認為成一個數組了，這個數組里面的元素的大容量比a數組里面的大
		//并且tmp在下一步要賦值給a
		


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

	//下面這個向上調整可以加上可以不加上
	// hp->a就是把a這個數組傳過去，hp->size-1就是最后一個元素的下標
	//AdjustUp(hp->a,hp->size-1);
}
//打印函數，把元素一個個打印出來，驗證你的代碼是否正確
void Print(HP* hp, int sz)
{
	for (int i = 0; i< sz; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}//這個是向下調整
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	//這里child沒分左右孩子，默認為左孩子
	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;//相應的順序大家看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)的意思就是，最后一個孩子的父親，n-1是最后一個孩子，把它看成N
		//然后（N）-1/2不就是我說的公式嘛
		//這個時候arr數組中的元素都已經相應的插入到a里面去了，但是還是亂序，不知道它是大堆還是小堆，這里我們要把它調成大堆，因為是升序
		//i= (n - 1 - 1) / 2意味著我們只需要從倒數第一個非葉子結點調整，如果我們從葉子結點調整的話，葉子結點也沒有孩子呀，碼農們想一下
		//這時候i--的意思就是調整完倒數第一個非葉子結點之后，就開始調整倒數第二個非葉子結點
	{
		//hp->a表示傳數組，n表示傳元素的個數，i表示開始調整大堆的位置
		AdjustDown(hp->a, n, i);
	}
	//上一行代碼---也就是}這個大括號的右半部分結束之后，我們的大堆就調好了
	//下一行代碼就是要開始排序了
	for (int end = n - 1; end >0; end--)
	{
		//你想，hp->a[0]肯定是這個堆里面的大的一個，然后把這個大的一個跟堆里面最后一個進行交換
		Swap(&hp->a[0], &hp->a[end]);
		//換完了之后，最后一個換到了第一個，這個時候亂序了，肯定不是大堆了，這個時候就開始把第一個向下調整
		//hp->a表示傳數組，end表示傳元素的個數，0表示開始調整大堆的位置
		AdjustDown(hp->a, end, 0);
		//調整完了之后又是一個大堆了，這個時候數組最后一個元素大，所以end--，這個時候相當于不要數組最后一個元素了，大的已經找到了
		//然后，這個不要最后一個元素之后，第一個元素就是大的了，然后再進行循環
		
		
		//為什么end不是>=0呢，你想，假如有5個數字，大的4個數字都找出來了，最后一個肯定是最小的呀
	}
}
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++)//把這個數組里面的元素一個個插入到HPDataType* a里面去
	{
		HeapPush(&hp,arr[i]);
	}
	Print(&hp, sz);
	Heapsort(&hp, sz);
	Print(&hp, sz);
	return 0;
}

?

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享題目：C語言版堆排序代碼講解（超級詳細）-創新互聯
當前路徑：http://m.newbst.com/article0/dcjoio.html

成都網站建設公司_創新互聯，為您提供網站設計公司、網頁設計公司、面包屑導航、網站策劃、標簽優化、網站收錄

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯