堆排序
首先介紹一下堆排序屬于選擇排序的一種類型。
其次就是他有點依賴于順序存儲樹判斷其孩子以及父節點的概念，接下來復習一下。
堆分為大根堆和小根堆
① 若滿?：L(i)≥L(2i)且L(i)≥L(2i+1) （1 ≤ i ≤n/2 ）—— ?根堆（?頂堆）
② 若滿?：L(i)≤L(2i)且L(i)≤L(2i+1) （1 ≤ i ≤n/2 ）—— ?根堆（?頂堆）
注意這里的判斷條件結合一下前面樹的節點判斷條件來看。
接下來介紹如何進行堆排序，
在大根堆中堆頂元素的關鍵字值最大，
。
接下里介紹一下給出一堆數組如何建立大根堆，這里一定注意結合樹來理解。
思路：把所有?終端結點都檢查?遍，是否滿??根堆的要求，如果不滿?，則進?調整
在順序存儲的完全?叉樹中，?終端結點編號 i≤?n/2?
簡單來說就是檢查數組的前一半元素（采取從后到前的順序）因為?終端結點編號 i≤?n/2?。檢查這一半的非終端節點是否滿足大根堆的定義看左右孩子是否都比他小
結合這個例子來看，你會發現一般的元素就是從下標4 開始算起，接下來就開始檢查9會發現左子樹大于根所以需要交換位置（包含數組中的位置，可以考慮采用swap來進行元素的交換。），如圖所示
接下來該檢查78了，會發現87比它大。所以需要交換元素。處理完同時掃描下一個元素也就是17。
掃描17發現左右孩子都比它大就需要選取最大的一個了這樣才能滿足大根堆的定義。
處理如下。
接著再處理53
53的處理有點特殊
53交換元素后還是不滿足定義，這時就需要再一次的下墜。
此時得到一個大根堆的樹形
接下來我們看一下代碼的實現以及解析
從上往下看，首先設置i為二分之length同時
因為為了方便操作第一個元素也就是數組0元素不存儲數據。然后調用
函數
接下來解析函數
首先設置數組0用來臨時存儲根節點，然后借用一個循環
注意這里的傳參上一個函數傳過來的i值（也就是用來算非終端節點的i）在本函數中用K來表示了，具體的比較函數的定義
理解了K然后我們繼續看循環，循環體重新設置了一個變量i等于2k用來找到孩子節點，同時注意i要小于數組長度否則沒有意義可能程序還會被臟數據污染。循環條件是
可以看為i=i*2
接下來進入循環體，
這一步是用來選取子節點里面較大的那個節點，如果
大，那么就讓i+1也就是孩子中大的那個的下標。如果沒有就說明時i大那就保持原本的。
如果
也就是暫存的元素（此時涉及到的非終端節點）大那就不需要交換位置此時這一棵子樹滿足大根堆的定義就可以直接跳出 循環執行
也就是原來的位置處
如果不滿足
也就是孩子大那就將孩子調整到K的位置然后修改K值再一次執行
此時注意循環條件
，再一次檢查調整過后是否還需要下墜才滿足大根堆的條件直到
即跳出來數組，此時這個判斷條件說明這個節點已經不能下墜了此時的節點一定是終端節點也就是葉子節點依據
來判斷的，如果是這樣的話也直接執行
，即將葉子節點的值設為暫存的元素值，因為它實在太小了，只能不斷地下墜到達葉子節點。具體的看一下接下來53的過程.
?
同時改該函數里面的i值判斷接下來的值是否符合標準。
再一次執行此時溢出數組了，結束循環。?
上面的代碼是建立大根堆，接下里我們介紹基于大根堆實現完整的排序?
?接下來看一下堆排序的完整代碼。?
接下來的才是完整堆排序的思想
堆排序：每?趟將堆頂元素加?有序?序列（與待排序序列中的最后?個元素交換）
并將待排序元素序列再次調整為?根堆（?元素不斷“下墜”）
第一步交換9 和87
然后新的大根堆需要length-1以方便重新排堆（讓87直接輸出到數組末尾同時重新拍大根堆不算87）
調整如下
再一次首元素和末尾元素
然后再一次調整剩下的元素的大根堆同時新大根堆的調整長度需要減1.
再次斷開一個元素，再次調整大根堆剩下操作如此往復即可
n-1趟 處理之后：
接下來我們整合調整過程
注意一下完整邏輯的代碼
這里第一步是建立了一個堆應該是如下圖所示的
此時定義i讓他指向最后一個元素用于交換首尾元素同時要實現上面斷掉元素的過程讓i--,進入循環交換首位元素然后調整大根堆，此時注意一下傳入參數的信息。
調整數組A以下標為1的根堆長度為i-1。再然后循環起來i--再一次交換元素，然后再一次調整，實現之前說過的調整趟數的過程，最后得出升序排序。
堆的插入刪除
首先聲明一下，減輕一下心里負擔的壓力，堆的刪除插入只要求弄懂手算過程沒有代碼，但是要求學會計算對比次數。
這里以小根堆為例演示一下
插入
插入13
注意小根堆規則，根要小于孩子。注意元素的上升，
1.首先對比，32和13發現13小然后就上升13
2.然后對比13和17，發現13需要上升
3.再次對比13和9，發現現在不需要上升了。
此時共發生了三次關鍵字的對比。
接下來插入一下46
發現只需要1次對比它不會上升。
接下來看一下刪除的操作
刪除
被刪除的元素?堆底元素替代，然后讓該
元素不斷“下墜”，直到?法下墜為?
元素被刪除了就會采用堆底的元素來代替。這里刪除13可以選取46來做代替，選取代替元素的規則（要求拆掉元素以后滿足二叉樹的定義所以只能拆掉46），
拆掉46以后還得讓其滿足小根堆的要求先需要對比孩子里面小的值，然后拿孩子里面小的值來和根對比
第一次17和45比較；第二次17和46比較下沉46；第三次52和32比較；第四次比較46和32下沉46
總共對比了4次注意若下方就一個孩子則下墜只涉及到一次對比就沒有孩子間的那次對比了。
接下來刪除65試試
為了符合二叉樹的規則只能借用46
第一次對比78和87，第二次對比78和46，對比結束
接下來總結一下
