說明：該系列博客整理自《算法導(dǎo)論(原書第二版)》，但更偏重于實用喜德，所以晦澀偏理論的內(nèi)容未整理山橄，請見諒。另外本人能力有限舍悯，如有問題航棱，懇請指正睡雇！
? ? 堆排序是一種原地排序法，即在任何時候饮醇，數(shù)組中只有常數(shù)個元素存儲在輸入數(shù)組以外它抱。由于該算法具有相當快的運行速度，且原地排序朴艰，所以結(jié)合了合并排序和插入排序的優(yōu)點观蓄。
1、堆
????（二叉）?堆?數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對象(如下圖所示)呵晚，它可以被視為一棵完全二叉樹蜘腌。樹中每個結(jié)點與數(shù)組中存放該結(jié)點值的那個元素對應(yīng)沫屡。樹的每一層都是填滿的饵隙，最后一層可能除外（最后一層從節(jié)點的左子樹開始填）。
????堆一般都用數(shù)組來表示沮脖，表示堆的數(shù)組?A?是一個具有兩個屬性的對象：?A.length?是數(shù)組中元素的個數(shù)金矛，?A.heap-size?是存放在?A?中的堆元素個數(shù)。雖然A[1...A.length]都可以包含有效值勺届，但A[A.heap-size]之后的元素都不屬于相應(yīng)的堆驶俊，所以有?A.heap-size?<=?A.length?。樹的根為?A?[ 1 ]免姿，給定了某個結(jié)點的下標?i?饼酿，其父結(jié)點?PARENT(i)?，左兒子?LEFT(i)?和右兒子?RIGHT(i)?的下標可以簡單的計算出來胚膊，公式如下（需要注意的是故俐，在一個好的堆排序的實現(xiàn)中，這三個過程通常是用宏或者內(nèi)聯(lián)函數(shù)實現(xiàn)）：
????????????????PARENT(i) = FLOOR(i / 2)
????????????????LEFT(i) = 2i
????????????????RIGHT(i) = 2i + 1
????????????????最后一個非葉子節(jié)點下標為length[A]/2后向下取整
以上公式成立的前提是i從1開始到n紊婉。如果i從0開始到n-1药版，則公式如下：
? ? ? ? ? ? ? ? PARENT(i) = FLOOR((i-1) / 2)
????????????????LEFT(i) = 2i + 1
????????????????RIGHT(i) = 2i + 2
????二叉堆有兩種：?最大堆?和?最小堆?(小根堆)。這兩種堆都要滿足各自的堆特性喻犁。在最大堆中槽片，最大堆特性是指除了根以外的每個結(jié)點?i?，有?A?[?PARENT(i)?] >=?A?[?i?]肢础，即某個結(jié)點的值至多和其父結(jié)點一樣大还栓，這樣，堆中的最大元素就存放在根結(jié)點中传轰。最小堆的組織方式剛好相反剩盒，最小堆特性是指除了根以外的每個結(jié)點?i?，有?A?[?PARENT(i)?] <=?A?[?i?]路召，最小堆的最小元素是在根部勃刨。
? ? 算法中使用何種堆：在堆排序算法中波材，我們使用的是最大堆。最小堆通常在構(gòu)造優(yōu)先隊列時使用身隐，具體將在書中6.5節(jié)廷区，優(yōu)先級隊列中講解。對于某個特定的應(yīng)用贾铝，我們將確切的指明需要的是最大堆還是最小堆隙轻；當某一性質(zhì)既適合最大堆，也適合最小堆時垢揩，我們就只使用堆這個詞玖绿。
????堆可以被看成是一棵樹，結(jié)點在堆中的高度定義為從本結(jié)點到葉子的最長簡單下降路徑上邊的數(shù)目叁巨；定義堆的高度為樹根的高度斑匪。因為具有n元素的堆是基于一顆完全二叉樹的，所以其高度為?Θ?(lg?n?)锋勺。堆結(jié)構(gòu)上的一些基本操作的運行時間至多與樹的高度成正比蚀瘸，為?O?(lg?n?)。下面將介紹幾個基本過程庶橱，并說明它們在排序算法和優(yōu)先級隊列數(shù)據(jù)結(jié)構(gòu)中如何使用：
? ? ? ? 1）贮勃、MAX-HEAPOFY?過程，運行時間為?O?(lg?n?)苏章，是保持最大堆性質(zhì)的關(guān)鍵
? ? ? ? 2）寂嘉、BUILD-MAX-HEAP?過程，以線性時間運行枫绅，可以在無序的輸入數(shù)組上構(gòu)造出最大堆
? ? ? ? 3）泉孩、HEAP-SORT?過程，運行時間為?O?(?n?lg?n?)撑瞧，對一個數(shù)組進行原地排序
? ? ? ? 4）棵譬、MAX-HEAP-INSERT?，?HEAP-EXTRACT-MAX?预伺，?HEAP-INCREASE-KEY?订咸，?HEAP-MAXIMUM?過程的運行時間為?O?(lg?n?)，可以讓堆結(jié)構(gòu)作為優(yōu)先級隊列使用酬诀。
2脏嚷、保持堆的性質(zhì)，即MAX-HEAPOFY?過程==>是建堆的基本過程
????MAX-HEAPIFY?過程的輸入為一個數(shù)組?A?和下標?i?瞒御。當?MAX-HEAPIFY?被調(diào)用時父叙，我們假定以?LEFT(i)?和?RIGHT(i)?為根的兩棵二叉樹都是最大堆，但這時?A?[?i?]可能小于其子女，這樣就違反了最大堆特性趾唱。?MAX-HEAPIFY?讓?A?[?i?]在最大堆中“下降”涌乳，使以?i?為根的子樹成為最大堆。
MAX-HEAPIFY(A, i)
????? l = LEFT(i)
????? r = RIGHT(i)
????? if l <= A.heap-size and A[l] > A[i]
????? ? ? largest = l
????? else
????? ? ? largest = i
????? if r <= A.heap-size and A[r] > A[largest]
????? ? ? largest = r
????? if largest != i
? ? ? ? ? exchange A[i] with A[largest]
????? ? ? MAX-HEAPIFY(A, largest)
????下圖描述了?MAX-HEAPIFY?的過程甜癞。在算法的每一步里夕晓，從元素?A?[?i?]，?A?[?LEFT(i)?]和?A?[?RIGHT(i)?]中找出最大的悠咱，并將其下標保存在?largest?中蒸辆。如果?A?[?i?]是最大的，則以?i?為根的子樹已是最大堆析既，程序結(jié)束躬贡。否則，交換?A?[?i?]和?A?[?largest?]眼坏，從而使?i?及其子女滿足堆性質(zhì)拂玻。下標為?largest?的結(jié)點在交換后的值為?A?[?i?]，以該結(jié)點為根的子樹可能又違反了最大堆性質(zhì)空骚。因而要對該子樹遞歸調(diào)用?MAX-HEAPIFY?纺讲。
當?MAX-HEAPIFY?作用在一棵以結(jié)點?i?為根的，大小為?n?的子樹上時囤屹，其運行時間為調(diào)整元素?A?[?i?]，?A?[?LEFT(i)?]和?A?[?RIGHT(i)?]的關(guān)系時所用的時間?Θ?(1)逢渔，加上對以?i?為結(jié)點的某個子結(jié)點為根的子樹遞歸調(diào)用?MAX-HEAPIFY?所需的時間肋坚。?i?結(jié)點的子樹大小至多為2?n?/ 3（最壞情況發(fā)生在最底層恰好半滿的時候），那么?MAX-HEAPIFY?的運行時間可表示為：?T?(?n?) <=?T?(2?n?/ 3) +?Θ?(1)肃廓。該遞歸式的解為?T?(?n?) =?O?(lg?n?)智厌。或者說盲赊，?MAX-HEAPIFY?作用于一個高度為?h?的結(jié)點所需的運行時間為?O?(?h?)铣鹏，因為數(shù)的高度為lg?n。
2哀蘑、建堆诚卸，即BUILD-MAX-HEAP?過程
????現(xiàn)在可以自底向上地用?MAX-HEAPIFY?來將一個數(shù)組?A?[ 1 ..?n?]（此處?n?=?A.length?）變成一個最大堆。因子數(shù)組?A?[?FLOOR(n / 2)?+ 1 ..?n?]中的元素都是樹中的葉子結(jié)點绘迁，它們都可以看做是只含一個元素的堆合溺，不用再通過MAX-HEAP過程降序來保證堆的性質(zhì)，所以建堆的循環(huán)過程為?FLOOR(A.length / 2)--->1缀台。過程?BUILD-MAX-HEAP?對樹中的每一個非葉子結(jié)點都調(diào)用了一次?MAX-HEAPIFY來建堆 棠赛。總結(jié)來說建堆的過程就是i從到FLOOR(A.length / 2)到1逐步保持堆特性的過程，即從葉子節(jié)點的父節(jié)點一級逐級向上保持堆性質(zhì)的過程！
BUILD-MAX-HEAP(A)
????A.heap-size = A.length
????for i = FLOOR(A.length / 2) downto 1
????????MAX-HEAPIFY(A, i)
下圖給出了?BUILD-MAX-HEAP?過程的一個例子睛约。
????我們可以計算出?BUILD-MAX-HEAP?運行時間的一個簡單上界：每次調(diào)用?MAX-HEAPIFY?的時間為?O?(lg?n?)鼎俘，共有?O?(?n?)次調(diào)用，故運行時間是?O?(?n?lg?n?)辩涝。盡管這個界是對的而芥，但從漸近意義上來說不夠緊確。
????實際上膀值，我們可以得到一個更加緊確的界棍丐。因為，在樹中不同高度的結(jié)點處運行?MAX-HEAPIFY?的時間不同沧踏，而大部分結(jié)點的高度都比較小歌逢。關(guān)于更緊確界的分析依賴于這樣的性質(zhì)：一個?n?元素堆的高度為FLOOR(lg?n?)，并且翘狱，在任意高度?h?上秘案，至多有CEIL(?n?/ 2(?h?+ 1))個結(jié)點。
????MAX-HEAPIFY?作用在高度為?h?的結(jié)點上的時間為?O?(?h?)潦匈，可以將?BUILD-MAX-HEAP?的代價表示為上確界：
????最終可以得出?BUILD-MAX-HEAP?過程運行時間的界為
????這說明可以在線性時間內(nèi)阱高，將一個無序數(shù)組建成一個最大堆。
