一步绸、什么是堆悴晰？
- 首先是一棵完全二叉樹趋艘；
- 大頂堆：每個結(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)整捶惜，即可完成處理Ｌ锩辍！Ｖㄆ摺汽久！
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/sort-heap-5.png" width="400" />
