復(fù)習(xí)之前學(xué)過的堆排序，發(fā)現(xiàn)掌握的不是特別牢固，又仔細(xì)閱讀了幾篇博文，整理出來這篇記錄。

1 堆排序介紹

1.1 與堆有關(guān)的概念

二叉樹：每個節(jié)點最多有兩個子節(jié)點的樹。
完全二叉樹：除了最后一層之外，每一層都被完全填充并且最后一層左對齊的二叉樹。
最大堆：每個父節(jié)點都大于孩子節(jié)點的完全二叉樹。
最小堆：每個父節(jié)點都小于孩子節(jié)點的完全二叉樹。

這里我們討論最大堆，在最大堆中，如果節(jié)點標(biāo)號從 1 開始，滿足如下條件：

• 父節(jié)點標(biāo)號為 i ，左孩子節(jié)點標(biāo)號為 i*2, 右孩子節(jié)點標(biāo)號為 i*2 + 1。
• 最后一個節(jié)點標(biāo)號為 j ,則它的父節(jié)點的標(biāo)號為 j // 2，也是最后一個有子節(jié)點。

1.2 堆排序

給定一個列表[90,50,80,16,30,60,70,10,2]，在上面講到，節(jié)點標(biāo)號從1開始滿足某些性質(zhì)方便表示，為了和下標(biāo)索引對應(yīng)起來，在列表最前端添加一個占位元素0,此時列表變?yōu)?code>[0,90,50,80,16,30,60,70,10,2]。
堆排序主要步驟如下：

• 首先我們將列表調(diào)整成一個最大堆。
• 此時堆首的元素最大，將它與堆最有一個元素交換。
• 將剩下的元素調(diào)整成一個最大堆。
• 循環(huán)執(zhí)行，直到需要調(diào)整的堆中只有一個元素。

2堆排序步驟詳解

• 將列表調(diào)整為一個最大堆，得到結(jié)果如下：

  
  
  初始的最大堆

• 將最大的堆頂元素與最后一個元素交換，即90與2交換，得到如下結(jié)果：
  

  將90與2交換后的堆

• 此時除了90剩下的元素構(gòu)成的堆已經(jīng)不是最大堆，調(diào)整剩下的元素，使它成為最大堆

  
  
  調(diào)整元素，使它成為最大堆

• 調(diào)整結(jié)果如下，然后繼續(xù)重復(fù)上述步驟，直到堆中只有一個元素。

  
  
  剩下的元素變?yōu)樽畲蠖?/div>

3 代碼

整體的排序分為 2 塊：

• 初始化最大堆
• 交換堆頂與堆尾元素
  注：
  1.在初始化最大堆的過程中，從最后一個有子節(jié)點開始，也就是從最后一個極小堆開始
  2.在隊首加入占位元素，如果直接用python內(nèi)置的list，用.insert(0)方法時間復(fù)雜度為O(n)，而用單鏈表時間復(fù)雜度僅為O(1)。文件頭需要加入from collections import deque

def heap_sort(l):
    # 加入占位元素
    L = deque(l)
    L.appendleft(0)
    
    Length = len(L) - 1 #最大索引下標(biāo)
    first_sort_count = Length // 2 # 最后一個有子節(jié)點索引下標(biāo)
    # 初始化最大堆， 從最后一個有子節(jié)點開始
    for i in range(first_sort_count):
        heap_adjust(L, first_sort_count - i, Length)
        
    # 開始排序
    for i in range(Length-1):
        swap_param(L, 1, Length-i)
        heap_adjust(L, 1, Length-i-1)
        
    return [L[i] for i in range(1, len(L))]

def heap_adjust(L, start, end):
    tmp = L[start]
    i = start
    j = i*2
    
    while j <= end:
        if (j<end) and (L[j]<L[j+1]):
            j += 1
        if tmp < L[j]:
            L[i] = L[j]
            i = j
            j = i*2
        else:
            break
    
    L[i] = tmp

def swap_param(L, i, j):
    L[i], L[j] = L[j], L[i]

4 時間和空間復(fù)雜度

空間復(fù)雜度：O(1)。就地排序，全程并沒有使用額外的空間。

時間復(fù)雜度：O(nlogn)。
分為初始化堆過程和每次選取最大數(shù)后重新建堆的過程。
1.初始化建堆過程時間：O(n)

首先要理解怎么計算這個堆化
假設(shè)高度為k，則從倒數(shù)第二層右邊的節(jié)點開始，這一層的節(jié)點都要執(zhí)行子節(jié)點比較然后交換（如果順序是對的就不用交換）；倒數(shù)第三層呢，則會選擇其子節(jié)點進行比較和交換，如果沒交換就可以不用再執(zhí)行下去了。如果交換了，那么又要選擇一支子樹進行比較和交換；
那么第 i 層的時間計算為：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第幾層，2^( i - 1) 表示該層上有多少個元素，( k - i) 表示子樹上要比較的次數(shù)，如果在最差的條件下，就是比較次數(shù)后還要交換；因為這個是常數(shù)，所以提出來后可以忽略；

S = 2^(k-2) * 1 + 2^(k-3)2+.....+2(k-2) + 2^(0)*(k-1) ===> 因為葉子層不用交換，所以i從 k-1 開始到 1；
這個等式求解:等式左右乘上2，然后和原來的等式相減，就變成了：
S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)。
除最后一項外，就是一個等比數(shù)列了，直接用求和公式：S = ；

S = 2^k -k -1；又因為k為完全二叉樹的深度，所以 (2^k) <= n < (2^k -1 )，總之可以認(rèn)為：k = logn
綜上所述得到：S = n - longn -1，所以時間復(fù)雜度為：O(n)。

2.重構(gòu)最大堆過程
在取出堆頂點放到對應(yīng)位置并把原堆的最后一個節(jié)點填充到堆頂點之后，需要對堆進行重建，只需要對堆的頂點調(diào)用heap_adjust()函數(shù)。
　　每次重建意味著有一個節(jié)點出堆，所以需要將堆的容量減一。heap_adjust()函數(shù)的時間復(fù)雜度k=log(n)，k為堆的層數(shù)。所以在每次重建時，隨著堆的容量的減小，層數(shù)會下降，函數(shù)時間復(fù)雜度會變化。重建堆一共需要n-1次循環(huán)，每次循環(huán)的比較次數(shù)為log(i)，則相加為：log2+log3+…+log(n-1)+log(n)≈log(n!)?？梢宰C明log(n!)和nlog(n)是同階函數(shù),所以時間復(fù)雜度為O(nlogn)。

最終的時間復(fù)雜度為O(nlogn)。