堆的概念
堆是一棵順序存儲的完全二叉樹。
其中每個結(jié)點(diǎn)的關(guān)鍵字都不大于其孩子結(jié)點(diǎn)的關(guān)鍵字，這樣的堆稱為小根堆。
其中每個結(jié)點(diǎn)的關(guān)鍵字都不小于其孩子結(jié)點(diǎn)的關(guān)鍵字，這樣的堆稱為大根堆。
舉例來說，對于n個元素的序列{R0, R1, ... , Rn}當(dāng)且僅當(dāng)滿足下列關(guān)系之一時，稱之為堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆，小頂堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆，大頂堆)
其中i=1,2,…,n/2向下取整;
如上圖所示，序列R{3, 8, 15, 31, 25}是一個典型的小根堆。
堆中有兩個父結(jié)點(diǎn)，元素3和元素8。
元素3在數(shù)組中以R[0]表示，它的左孩子結(jié)點(diǎn)是R[1]，右孩子結(jié)點(diǎn)是R[2]。
元素8在數(shù)組中以R[1]表示，它的左孩子結(jié)點(diǎn)是R[3]，右孩子結(jié)點(diǎn)是R[4]，它的父結(jié)點(diǎn)是R[0]?？梢钥闯?，它們滿足以下規(guī)律：
設(shè)當(dāng)前元素在數(shù)組中以R[i]表示，那么，
(1) 它的左孩子結(jié)點(diǎn)是：R[2i+1];
(2) 它的右孩子結(jié)點(diǎn)是：R[2i+2];
(3) 它的父結(jié)點(diǎn)是：R[(i-1)/2];
(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
堆排序
堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序。
堆排序基本思想及步驟
堆排序的基本思想是：將待排序序列構(gòu)造成一個大頂堆，此時，整個序列的最大值就是堆頂?shù)母?jié)點(diǎn)。將其與末尾元素進(jìn)行交換，此時末尾就為最大值。然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復(fù)執(zhí)行，便能得到一個有序序列了
步驟一 構(gòu)造初始堆。將給定無序序列構(gòu)造成一個大頂堆（一般升序采用大頂堆，降序采用小頂堆)。
1.假設(shè)給定無序序列結(jié)構(gòu)如下：
2.此時我們從最后一個非葉子結(jié)點(diǎn)開始（葉結(jié)點(diǎn)自然不用調(diào)整，第一個非葉子結(jié)點(diǎn) arr.length/2-1=5/2-1=1，也就是下面的6結(jié)點(diǎn)），從左至右，從下至上進(jìn)行調(diào)整。
3.找到第二個非葉節(jié)點(diǎn)4，由于[4,9,8]中9元素最大，4和9交換。
步驟二 將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換。
a.將堆頂元素9和末尾元素4進(jìn)行交換
再簡單總結(jié)下堆排序的基本思路：
a.將無需序列構(gòu)建成一個堆，根據(jù)升序降序需求選擇大頂堆或小頂堆;
b.將堆頂元素與末尾元素交換，將最大元素"沉"到數(shù)組末端;
c.重新調(diào)整結(jié)構(gòu)，使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個序列有序。
堆排序是一種選擇排序，整體主要由構(gòu)建初始堆+交換堆頂元素和末尾元素并重建堆兩部分組成。其中構(gòu)建初始堆經(jīng)推導(dǎo)復(fù)雜度為O(n)，在交換并重建堆的過程中，需交換n-1次，而重建堆的過程中，根據(jù)完全二叉樹的性質(zhì)，[log2(n-1),log2(n-2)...1]逐步遞減，近似為nlogn。所以堆排序時間復(fù)雜度一般認(rèn)為就是O(nlogn)級
注意：
請?zhí)貏e特別注意: 初始化大頂堆時 是從最后一個有子節(jié)點(diǎn)開始往上調(diào)整最大堆。而堆頂元素(最大數(shù))與堆最后一個數(shù)交換后，需再次調(diào)整成大頂堆，此時是從上往下調(diào)整的。
算法分析：
堆排序算法的總體情況
時間復(fù)雜度
堆的存儲表示是順序的。因?yàn)槎阉鶎?yīng)的二叉樹為完全二叉樹，而完全二叉樹通常采用順序存儲方式。
當(dāng)想得到一個序列中第k個最小的元素之前的部分排序序列，最好采用堆排序。
因?yàn)槎雅判虻?strong>時間復(fù)雜度是O(n+klog2n)，若k≤n/log2n，則可得到的時間復(fù)雜度為O(n)。
詳解：
1.堆排序的時間復(fù)雜度，主要在初始化堆過程和每次選取最大數(shù)后重新建堆的過程；
初始化建堆過程時間：O(n)
推算：
首先要理解怎么計(jì)算這個堆化過程所消耗的時間，可以直接畫圖去理解；
假設(shè)高度為k，則從倒數(shù)第二層右邊的節(jié)點(diǎn)開始，這一層的節(jié)點(diǎn)都要執(zhí)行子節(jié)點(diǎn)比較然后交換（如果順序是對的就不用交換）；倒數(shù)第三層呢，則會選擇其子節(jié)點(diǎn)進(jìn)行比較和交換，如果沒交換就可以不用再執(zhí)行下去了。如果交換了，那么又要選擇一支子樹進(jìn)行比較和交換；
那么總的時間計(jì)算為：s = 2^( i - 1 ) * ( k - i )；
其中 i 表示第幾層，2^( i - 1) 表示該層上有多少個元素，( k - i) 表示子樹上要比較的次數(shù)，如果在最差的條件下，就是比較次數(shù)后還要交換；因?yàn)檫@個是常數(shù)，所以提出來后可以忽略；
即S = 2^(k-2) * 1 + 2^(k-3) * 2.....+2*(k-2)+2^0 *(k-1) ===> 因?yàn)槿~子層不用交換，所以i從 k-1 開始到 1結(jié)束。
這個等式求解，我想高中已經(jīng)會了：等式左右乘上2，然后和原來的等式相減，就變成了：
S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)
除最后一項(xiàng)外，就是一個等比數(shù)列了，直接用求和公式：
S = { a1[ 1- (q^n) ] } / (1-q)；
S = 2^k -k -1；
又因?yàn)閗為完全二叉樹的深度，所以 (2^k) <= n < (2^k -1 )，總之可以認(rèn)為：k = logn （實(shí)際計(jì)算得到應(yīng)該是 log(n+1) < k <= logn ）;
綜上所述得到：S = n - longn -1，所以時間復(fù)雜度為：O(n)
2.更改堆元素后重建堆時間：O(nlogn)
推算過程：
1、循環(huán) n -1 次，每次都是從根節(jié)點(diǎn)往下循環(huán)查找，所以每一次時間是 logn，總時間：logn(n-1) = nlogn - logn ；
綜上所述：堆排序的時間復(fù)雜度為：O(nlogn)
空間復(fù)雜度
因?yàn)槎雅判蚴蔷偷嘏判颍?strong>空間復(fù)雜度為常數(shù)：O(1）
算法穩(wěn)定性
堆排序是一種不穩(wěn)定的排序方法。
因?yàn)樵诙训恼{(diào)整過程中，關(guān)鍵字進(jìn)行比較和交換所走的是該結(jié)點(diǎn)到葉子結(jié)點(diǎn)的一條路徑，
因此對于相同的關(guān)鍵字就可能出現(xiàn)排在后面的關(guān)鍵字被交換到前面來的情況。
引自：
1.作者： dreamcatcher-cx
出處： http://www.cnblogs.com/chengxiao/
2.出處：https://www.cnblogs.com/jingmoxukong/p/4303826.html
3.出處：http://blog.csdn.net/yuzhihui_no1/article/details/44258297
