一步绸、什么是堆悴晰?
- 首先是一棵完全二叉樹趋艘;
- 大頂堆:每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值;
- 小頂堆:每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值膳殷;
-
根結(jié)點(diǎn)一定是堆中所有結(jié)點(diǎn)最大或最胁俾狻九火;
heap
二、堆排序(Heap Sort)
- 將待排序的序列構(gòu)成一個大(胁嵴小)頂堆岔激,然后根據(jù)堆的性質(zhì),每次將堆頂元素(根結(jié)點(diǎn))輸出作為呆排序有序序列的元素是掰,然后調(diào)整剩余元素成為新的堆虑鼎,反復(fù)的操作直到堆中所有元素全部輸出,最終得到一個有序序列键痛;
- 一顆有n個節(jié)點(diǎn)的完全二叉樹炫彩,對其任意節(jié)點(diǎn)i,原則如下:
- 如果i=1絮短,則為根節(jié)點(diǎn)江兢,無雙親
- 如果2i>n,則節(jié)點(diǎn)i沒有左孩子
- 如果2i+1>n丁频,則節(jié)點(diǎn)i沒有右孩子
以下內(nèi)容借用 勇哥的分析
其實(shí)堆在內(nèi)存中還是采用原來的數(shù)組存儲杉允,只不過是在交換元素之間的位置,下面我們一邊看代碼實(shí)現(xiàn)(借用大話數(shù)據(jù)結(jié)構(gòu)的代碼)
三席里、代碼分析
堆排序 = 數(shù)組預(yù)處理(堆)+ 排序(swap)
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-heap-2.png" width="600" />
要排序的隊(duì)列是{50,10,90,30,70,40,80,60,20},這段代碼就是我們說的叔磷,通過堆將數(shù)組的最大值處理到數(shù)組的下標(biāo)1的位置上,然后用swap函數(shù)(排序)取走(這里它是交換到最后一個位置)奖磁,然后再用堆將數(shù)組重新處理改基,等待下一次比對!
這里又出現(xiàn)了新問題咖为,為什么預(yù)處理的時候秕狰,循環(huán)是從L->lenth/2開始的?案疲?封恰??
看看下面這張圖褐啡,在沒有形成堆前,我們可以把這個數(shù)組看成這棵樹鳖昌,循環(huán)的次數(shù)就是這棵樹的層數(shù)备畦,看看四個灰色節(jié)點(diǎn)和其葉子節(jié)點(diǎn)的值就能找到規(guī)律
也就是:
- s=>30, 2*s=>60, 2*s+1=>20
- s=>90, 2*s=>40, 2*s+1=>80
- s=>10, 2*s=>30, 2*s+1=>70
- s=>50, 2*s=>10, 2*s+1=>90
根據(jù)這個規(guī)律,s從L->length/2開始许昨,自下而上的求每個子樹的最大值懂盐,然后換至根節(jié)點(diǎn)(子樹),然后這個子樹根節(jié)點(diǎn)又會成為上一層節(jié)點(diǎn)的孩子節(jié)點(diǎn)
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-heap-3.png" width="300" />
最后代碼實(shí)現(xiàn)就是下面這張圖,可以看到里面寫了注釋糕档,其實(shí)就是自下而上莉恼,自右至左的按照剛才那棵樹的位置拌喉,將最大值一步步的換到根節(jié)點(diǎn)的過程。
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-heap-4.png" width="600" />
在每次swap將最小值交換至下標(biāo)1的位置上后俐银,調(diào)用HeapAdjust函數(shù)尿背,只需要對第一層,也就是根節(jié)點(diǎn)進(jìn)行調(diào)整捶惜,即可完成處理L锩辍!Vㄆ摺汽久!
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-heap-5.png" width="400" />