什么是堆

堆是一種叫做完全二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)，可以分為大根堆，小根堆，而堆排序就是基于這種結(jié)構(gòu)而產(chǎn)生的一種程序算法。

創(chuàng)新互聯(lián)建站主營(yíng)涇川網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,重慶APP軟件開(kāi)發(fā),涇川h5成都小程序開(kāi)發(fā)搭建,涇川網(wǎng)站營(yíng)銷(xiāo)推廣歡迎涇川等地區(qū)企業(yè)咨詢堆的分類(lèi)

大根堆:每個(gè)節(jié)點(diǎn)的值都大于或者等于他的左右孩子節(jié)點(diǎn)的值

小根堆:每個(gè)結(jié)點(diǎn)的值都小于或等于其左孩子和右孩子結(jié)點(diǎn)的值

兩種結(jié)構(gòu)映射到數(shù)組為:

大根堆:

小根堆:

//父-->子:i--->左孩子:2*i+1, 右孩子:2*i+2;
//子-->父:i--->(i-1)/2;?(i為下標(biāo)元素)

排序思想

1.首先將待排序的數(shù)組構(gòu)造成一個(gè)大根堆，此時(shí)，整個(gè)數(shù)組的大值就是堆結(jié)構(gòu)的頂端

2.將頂端的數(shù)與末尾的數(shù)交換，此時(shí)，末尾的數(shù)為大值，剩余待排序數(shù)組個(gè)數(shù)為n-1

3.將剩余的n-1個(gè)數(shù)再構(gòu)造成大根堆，再將頂端數(shù)與n-1位置的數(shù)交換，如此反復(fù)執(zhí)行，便能得到有序數(shù)組

注意:升序用大根堆，降序就用小根堆(默認(rèn)為升序)

構(gòu)造堆

那么如何構(gòu)造大根堆呢?

首先我們給定一個(gè)無(wú)序的序列，將其看做一個(gè)堆結(jié)構(gòu)，一個(gè)沒(méi)有規(guī)則的二叉樹(shù)，將序列里的值按照從上往下，從左到右依次填充到二叉樹(shù)中。

對(duì)于一個(gè)完全二叉樹(shù)，在填滿的情況下（非葉子節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)），每一層的元素個(gè)數(shù)是上一層的二倍，根節(jié)點(diǎn)數(shù)量是1，所以最后一層的節(jié)點(diǎn)數(shù)量，一定是之前所有層節(jié)點(diǎn)總數(shù)+1，所以，我們能找到最后一層的第一個(gè)節(jié)點(diǎn)的索引，即節(jié)點(diǎn)總數(shù)/2（根節(jié)點(diǎn)索引為0），這也就是第一個(gè)葉子節(jié)點(diǎn)，所以第一個(gè)非葉子節(jié)點(diǎn)的索引就是第一個(gè)葉子結(jié)點(diǎn)的索引-1。那么對(duì)于填不滿的二叉樹(shù)呢？這個(gè)計(jì)算方式仍然適用，當(dāng)我們從上往下，從左往右填充二叉樹(shù)的過(guò)程中，第一個(gè)葉子節(jié)點(diǎn)，一定是序列長(zhǎng)度/2，所以第最后一個(gè)非葉子節(jié)點(diǎn)的索引就是 arr.len / 2 -1，對(duì)于此圖數(shù)組長(zhǎng)度為5，最后一個(gè)非葉子節(jié)點(diǎn)為5/2-1=1，即為6這個(gè)節(jié)點(diǎn)

那么如何構(gòu)建呢？ 我們找到了最后一個(gè)非葉子節(jié)點(diǎn)，即元素值為6的節(jié)點(diǎn)，比較它的左右節(jié)點(diǎn)中大的一個(gè)的值，是否比他大，如果大就交換位置。

在這里5小于6,而9大于6，則交換6和9的位置

找到下一個(gè)非葉子節(jié)點(diǎn)4，用它和它的左右子節(jié)點(diǎn)進(jìn)行比較，4大于3，而4小于9，交換4和9位置

此時(shí)發(fā)現(xiàn)4小于5和6這兩個(gè)子節(jié)點(diǎn)，我們需要進(jìn)行調(diào)整，左右節(jié)點(diǎn)5和6中，6大于5且6大于父節(jié)點(diǎn)4，因此交換4和6的位置

此時(shí)我們就構(gòu)造出來(lái)一個(gè)大根堆,下來(lái)進(jìn)行排序

首先將頂點(diǎn)元素9與末尾元素4交換位置，此時(shí)末尾數(shù)字為大值。排除已經(jīng)確定的大元素，將剩下元素重新構(gòu)建大根堆

一次交換重構(gòu)如圖:

此時(shí)元素9已經(jīng)有序，末尾元素則為4(每調(diào)整一次，調(diào)整后的尾部元素在下次調(diào)整重構(gòu)時(shí)都不能動(dòng))

二次交換重構(gòu)如圖:

最終排序結(jié)果:?

由此，我們可以歸納出堆排序算法的步驟：

1. 把無(wú)序數(shù)組構(gòu)建成二叉堆。

2. 循環(huán)刪除堆頂元素，移到集合尾部，調(diào)節(jié)堆產(chǎn)生新的堆頂。

當(dāng)我們刪除一個(gè)大堆的堆頂（并不是完全刪除，而是替換到最后面），經(jīng)過(guò)自我調(diào)節(jié)，第二大的元素就會(huì)被交換上來(lái)，成為大堆的新堆頂。

正如上圖所示，當(dāng)我們刪除值為9的堆頂節(jié)點(diǎn)，經(jīng)過(guò)調(diào)節(jié)，值為6的新節(jié)點(diǎn)就會(huì)頂替上來(lái)；當(dāng)我們刪除值為6的堆頂節(jié)點(diǎn)，經(jīng)過(guò)調(diào)節(jié)，值為5的新節(jié)點(diǎn)就會(huì)頂替上來(lái).......

由于二叉堆的這個(gè)特性，我們每一次刪除舊堆頂，調(diào)整后的新堆頂都是大小僅次于舊堆頂?shù)墓?jié)點(diǎn)。那么我們只要反復(fù)刪除堆頂，反復(fù)調(diào)節(jié)二叉堆，所得到的集合就成為了一個(gè)有序集合，

堆排序是不穩(wěn)定的排序，空間復(fù)雜度為O(1),平均的時(shí)間復(fù)雜度為O(nlogn),最壞情況下也穩(wěn)定在O(nlogn)?

代碼示例:

void HeapAdjust(int* arr, int start, int end)
{
	int tmp = arr[start];
	for (int i = 2 * start + 1; i<= end; i = i * 2 + 1)
	{
		if (i< end&& arr[i]< arr[i + 1])//有右孩子并且左孩子小于右孩子
		{
			i++;
		}//i一定是左右孩子的大值
		if (arr[i] >tmp)
		{
			arr[start] = arr[i];
			start = i;
		}
		else
		{
			break;
		}
	}
	arr[start] = tmp;
}
void HeapSort(int* arr, int len)
{
	//第一次建立大根堆，從后往前依次調(diào)整
	for(int i=(len-1-1)/2;i>=0;i--)
	{
		HeapAdjust(arr, i, len - 1);
	}
	//每次將根和待排序的最后一次交換，然后在調(diào)整
	int tmp;
	for (int i = 0; i< len - 1; i++)
	{
		tmp = arr[0];
		arr[0] = arr[len - 1-i];
		arr[len - 1 - i] = tmp;
		HeapAdjust(arr, 0, len - 1-i- 1);
	}
}
int main()
{
	int arr[] = { 9,5,6,3,5,3,1,0,96,66 };
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
	printf("排序后為:");
	for (int i = 0; i< sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

排序結(jié)果:

路過(guò)有幫助麻煩點(diǎn)個(gè)贊再走！博主畫(huà)圖不容易┭┮﹏┭┮

2022/11/19 補(bǔ)充

這篇文章寫(xiě)的也挺早的了，今天抽空重新補(bǔ)充一下，因?yàn)楹芏嗯笥阉叫盼艺f(shuō)是沒(méi)看懂或者怎么樣的，(寫(xiě)的早，文筆表達(dá)確實(shí)有限)。我今天就再拿文字和簡(jiǎn)單的圖把思路說(shuō)一下，補(bǔ)充的我按照構(gòu)建小頂堆，就是從大到小排序一組數(shù)字。也有很多朋友問(wèn)啊大根堆構(gòu)建出來(lái)堆頂是大的元素，你最后排序輸出可又是從小到大，問(wèn)出這些問(wèn)題就說(shuō)明你沒(méi)有好好看步驟。

再提一嘴，像數(shù)據(jù)結(jié)構(gòu)優(yōu)先隊(duì)列這種他底層就是按照大根堆的方式去實(shí)現(xiàn)的，自動(dòng)排序取出優(yōu)先級(jí)最高的(默認(rèn)是元素最小)，也就是從小到大排

補(bǔ)充：

理解堆排序，他其實(shí)就是對(duì)于一組數(shù)去進(jìn)行排序(這里放在數(shù)組里)，而我們所說(shuō)的大根堆，小根堆都是邏輯上的讓我們?nèi)ダ斫馀判蛩惴?，千萬(wàn)別混為一談迷糊了

還是這么一組無(wú)序的數(shù)字，我們把它邏輯構(gòu)造成一個(gè)完全二叉樹(shù)

我們這里按照從大到小排序，構(gòu)建小根堆的大致思路來(lái)說(shuō)

我們堆排序的步驟就是這樣

先把這個(gè)最初的堆去?給他構(gòu)建成一個(gè)小根堆，所謂小根堆就是堆頂元素最小

注意構(gòu)建的時(shí)候就需要我們找分支結(jié)點(diǎn)，我最上面提到的那數(shù)學(xué)公式，我們從這個(gè)分支結(jié)點(diǎn)開(kāi)始把它的父結(jié)點(diǎn)這么一個(gè)小樹(shù)弄成小根堆，再往上跳，從他的父結(jié)點(diǎn)開(kāi)始，找雙親把他們這一部分調(diào)整成最小堆。依次類(lèi)推，說(shuō)白了就是從下面局部構(gòu)成小根堆，一點(diǎn)一點(diǎn)，最后整體全局構(gòu)建小頂堆。這樣構(gòu)建之后你全局的堆頂才是最小的一個(gè)元素，這才是所謂的完整的一次構(gòu)建。體現(xiàn)在數(shù)組上就是你數(shù)組首元素現(xiàn)在是最小的，因?yàn)槟愣秧斁痛碇?號(hào)下標(biāo)元素不是。（大根堆就是上面元素是大的而已，怎么構(gòu)建還都是一樣啊，就是把大元素往上覆蓋，判斷條件變了而已）

現(xiàn)在你首元素最小了，說(shuō)明邏輯上就是個(gè)小根堆了，你是怎么倒敘呢？不就是首元素和尾元素交換。然后你數(shù)組最后面不就成了最小的（這是體現(xiàn)在數(shù)組上的），那么同樣體現(xiàn)在此時(shí)這個(gè)小根堆上，就是把堆頂元素和尾巴一交換。

那為什么每次交換完，需要我尾巴元素不能動(dòng)，去構(gòu)建剩余元素呢？你每構(gòu)建完一次小根堆，交換元素，你此時(shí)在數(shù)組上是不是把最小的元素放在末尾了，說(shuō)明已經(jīng)確定了，那我們就不需要?jiǎng)恿耍覀円獎(jiǎng)拥木褪菙?shù)組那些沒(méi)確定的元素，在這些里面去找一個(gè)最小的。那么這一步體現(xiàn)在堆上，是不是需要我們重新再除了尾巴元素以外剩下結(jié)點(diǎn)上從局部到整體去構(gòu)建小根堆了。

再一次構(gòu)建，是不是這里面最小的跑到堆頂了（數(shù)組里就是最小的跑到了首元素位置），再去交換首元素和沒(méi)有排好序的這一段數(shù)組的最后一個(gè)下標(biāo)位置，交互完了再重構(gòu).....

舉個(gè)例子，6,2,1,4? ?這么一組數(shù)我們第一次構(gòu)建小根堆之后，1就跑到了堆頂，也就是跑到了數(shù)組首元素1，數(shù)組此時(shí)為1 * * *，和最后一個(gè)元素交換，就成了* * * 1，那么這個(gè)時(shí)候1就已經(jīng)確定了，我們下來(lái)要做的是把* * *這三個(gè)構(gòu)建出一個(gè)小根堆，這三個(gè)里最小的放在首元素，

比方說(shuō)是2 * * 1，我們交換2和這次沒(méi)確定的數(shù)組最后一個(gè)元素，成了* * 2 1，此時(shí)2 和1已經(jīng)確定了，我們?cè)偃ナＯ聝蓚€(gè)* *去構(gòu)建，去交換，最后得到 6 4 2 1

還是這三步：

1. 把無(wú)序的這一串?dāng)?shù)，想象成一個(gè)堆，根據(jù)要求去從局部到整體構(gòu)建一個(gè)大頂堆或者小頂堆，我們要的就是此時(shí)這個(gè)堆頂元素
2. 把堆頂元素和末尾元素交換，就是把堆頂元素（數(shù)組首元素）換到了數(shù)組的末端
3. 重新調(diào)整除了數(shù)組末端(已經(jīng)確定順序的元素)以外的元素，去構(gòu)建堆，然后交換堆頂和當(dāng)前末尾，構(gòu)建，交換堆頂和當(dāng)前末尾..

給個(gè)小根堆的測(cè)試代碼

void FF(vector& nums, int start, int end)//構(gòu)建最小堆
{
	int i = start, j = 2*i+1;
	int tmp = nums[i];
	while (j<=end)
	{
		if (j< end&& nums[j] >nums[j + 1]) j += 1;
		if (tmp<= nums[j])break;
		nums[i] = nums[j];
		i = j;
		j = i * 2 + 1;
	}
	nums[i] = tmp;
}
void SortFF(vector&nums, int n)//堆排序
{
	//if ( nums.size()==0||n< 2)return;
	int pos = (((n - 1) - 1) / 2);
	while (pos >= 0)//從下往上局部，最后整體去調(diào)整成小頂堆
	{
		FF(nums, pos,n - 1);
		pos-=1;
	}
	//調(diào)整完了此時(shí)這個(gè)二叉堆最上面就是最小的數(shù)
	//在數(shù)組里就是一頓調(diào)整之后，第一個(gè)元素是最小的

	pos = n - 1;//讓pos指向數(shù)組最后一個(gè)位置
	while (pos >0)
	{
		swap(nums[0], nums[pos]);//交換第一個(gè)元素和pos指向的位置第一次完了之后，最小元素就在數(shù)組最后
		pos-=1;    //讓pos指向數(shù)組往前一個(gè)位置，相當(dāng)于最后一個(gè)元素是最小的已經(jīng)確認(rèn)
		FF(nums,0,pos);//那么就是開(kāi)始重新調(diào)整除過(guò)已經(jīng)確認(rèn)元素剩下那一段數(shù)組元素
		                 //這下又把這一段數(shù)組里面最小的放在堆頂
		                 //再次進(jìn)入循環(huán)，去交換位置	                
	}
}

int main()
{
	vectorvv{53,17,78,9,45,65,87,23};
	
	SortFF(vv,vv.size());
	for (auto const& x : vv) {
		cout<< x<< " ";
	}
	return 0;
}

就到這里了，我大白話把整個(gè)過(guò)程描述了一遍

你是否還在尋找穩(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)查看詳情吧

名稱(chēng)欄目：堆排序詳細(xì)圖解（通俗易懂）-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://aaarwkj.com/article14/pppge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、定制網(wǎng)站、動(dòng)態(tài)網(wǎng)站、網(wǎng)站導(dǎo)航、搜索引擎優(yōu)化、網(wǎng)站收錄

廣告

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