大家好栖忠，我是“Stephen·謝”裁蚁，今天講一下關(guān)于數(shù)據(jù)結(jié)構(gòu)“堆”以及“堆排序”算法的相關(guān)內(nèi)容卵史。
“堆結(jié)構(gòu)”
前面的好幾篇文章都講到了樹(shù)的結(jié)構(gòu)，今天要講的“堆”其實(shí)也是樹(shù)結(jié)構(gòu)的一種痛黎，我們看下圖：
很明顯予弧，我們發(fā)現(xiàn)它們都是“二叉樹(shù)”，并且還是“完全二叉樹(shù)”湖饱，左圖中根節(jié)點(diǎn)是所有元素中最大的掖蛤，右圖中根節(jié)點(diǎn)是所有元素中最小的，左圖中每個(gè)節(jié)點(diǎn)都比它左右孩子要大井厌，右圖中每個(gè)節(jié)點(diǎn)都比它左右孩子要小坠七。這便是我們要講的“堆”結(jié)構(gòu)。
堆結(jié)構(gòu)中旗笔，每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子節(jié)點(diǎn)的值稱為“大頂堆”彪置，每個(gè)節(jié)點(diǎn)的值都小于或等于其左右孩子節(jié)點(diǎn)的值稱為“小頂堆”。
注意蝇恶，根節(jié)點(diǎn)一定是堆中所有節(jié)點(diǎn)最大（腥）者，較大（写榛 ）的節(jié)點(diǎn)靠近根節(jié)點(diǎn)潘懊。（但也不絕對(duì)，如右圖小頂堆中60贿衍、40均小于70授舟，但他們并沒(méi)有比70更靠近根節(jié)點(diǎn)）
我們?nèi)绻凑铡皩有虮闅v”的方式給節(jié)點(diǎn)從1號(hào)開(kāi)始編號(hào)，則節(jié)點(diǎn)之間滿足以下關(guān)系：
此公式一定要看懂贸辈，一定要理解i释树，2i，2i+1，[n/2]對(duì)于堆結(jié)構(gòu)而言代表著什么奢啥。
“堆排序算法”
堆結(jié)構(gòu)的根節(jié)點(diǎn)是最大或最小的這個(gè)特點(diǎn)給了我們靈感秸仙，我們或許可以利用堆的這個(gè)特點(diǎn)來(lái)進(jìn)行排序的實(shí)現(xiàn)。
堆排序(Heap Sort)就是利用堆（假設(shè)利用大頂堆）進(jìn)行排序的方法桩盲。它的基本思想是：將待排序的序列構(gòu)成一個(gè)大頂堆寂纪，此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)赌结，再將它移走（其實(shí)就是將其與堆數(shù)組的末尾元素交換捞蛋，此時(shí)末尾元素就是最大值），然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)大頂堆柬姚，這樣就會(huì)得到這n個(gè)元素中的次小值襟交。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列了伤靠。
上面圖例中對(duì)堆排序思想的展示再清晰不過(guò)了。不過(guò)現(xiàn)實(shí)中我們需要解決兩個(gè)問(wèn)題啼染，第一：如何由一個(gè)無(wú)序序列構(gòu)建成一個(gè)堆宴合；第二：如何在得到堆頂元素后，調(diào)整剩余的元素成為一個(gè)新的堆迹鹅。
上代碼截圖：
從代碼中可以看出卦洽，整個(gè)排序過(guò)程分為兩個(gè)循環(huán)，第一個(gè)循環(huán)要完成的就是將現(xiàn)在的待排序序列構(gòu)建成一個(gè)大頂堆斜棚，第二個(gè)循環(huán)要完成的就是逐步將每個(gè)最大值的根節(jié)點(diǎn)與末尾元素交換阀蒂，并再調(diào)整其成為一個(gè)大頂堆。用動(dòng)態(tài)圖形象地表示如下：
解釋一下無(wú)非就兩點(diǎn)：
1弟蚀、 從下往上蚤霞，從右往左地順序查找每個(gè)非葉子結(jié)點(diǎn)，對(duì)比子結(jié)點(diǎn)义钉，與最大結(jié)點(diǎn)交換位置昧绣，交換的新位置再與其子結(jié)點(diǎn)比較、移動(dòng)捶闸，遍歷后最終找到最大值夜畴。
2、把堆頂和最后的元素交換位置删壮，排除最后的位置贪绘，重復(fù)1步驟，找到遍歷后的最大值央碟，放到倒數(shù)第二的位置税灌，依次直到結(jié)束。
堆排序復(fù)雜度分析
堆排序運(yùn)行時(shí)間主要是消耗在初始構(gòu)建堆和在重建堆時(shí)的反復(fù)篩選上。在構(gòu)建堆的過(guò)程中垄琐，對(duì)每個(gè)終端節(jié)點(diǎn)最多進(jìn)行兩次比較操作边酒，因此整個(gè)排序堆的時(shí)間復(fù)雜度為O(n)。在正式排序時(shí)狸窘，第i次取堆頂記錄重建堆需要用O(logi)的時(shí)間墩朦，并需要取n-1次堆頂記錄，因此總體來(lái)說(shuō)翻擒，堆排序的時(shí)間復(fù)雜度為O(nlogn)氓涣。由于堆排序?qū)υ紨?shù)據(jù)的排序狀態(tài)并不敏感，因此它無(wú)論是最好陋气、最壞和平均時(shí)間復(fù)雜度均為O(nlogn)劳吠。在這性能上顯然要遠(yuǎn)遠(yuǎn)好過(guò)于冒泡、選擇巩趁、插入的O(n2)的時(shí)間復(fù)雜度了痒玩。
空間復(fù)雜度上，它只有一個(gè)用來(lái)交換的暫存單元议慰，也是非常不錯(cuò)蠢古。不過(guò)由于記錄的比較和交換是跳躍式進(jìn)行，因此堆排序也是一種不穩(wěn)定的排序方法别凹。另外草讶，由于初始構(gòu)建堆排序需要的比較次數(shù)較多，因此炉菲，它不適合待排序序列個(gè)數(shù)較少的情況堕战。
