堆排序(heap sort)

來自專欄演算法導論4 人贊了文章

本文介紹另一種排序演算法，即heap sort，其具有以下特點：

與合併排序類似，堆排序運行時間為，快於插入排序
與插入排序類似，堆排序為in-place排序演算法，在任何時候，數組中只有常熟個元素存儲在輸入數組以外

因此heap sort將 merge sort的速度快和插入排序的in place特點結合起來。

堆排序還引入了另一種演算法設計技術，即利用某種數據結構來管理演算法之行中的信息，在這裡採用了堆。

1. heap

堆數據結構是一種數組對象，可以被視為一棵完全二叉樹，樹中每個節點與數組中存放該節點值的元素對應。樹的每一層是滿的，最後一層除外（最後一層從一個節點的左子樹開始填）。

堆可以用數組來進行實現。樹的根為，給定了某個節點，其父節點 ,左子節點和右子節點在數組中的下標可以簡單計算如下：

用0作為數組起始下標，python實現如下所示

def left(i): return 2 * (i + 1) - 1def right(i): return 2 * (i + 1)def parent(): return (i + 1) * 2 - 1

二叉堆有兩種，最大堆和最小堆。最大堆是指父節點比子節點大，最大元素存放在根節點，並且在以一個節點為根的子樹中，各節點的值都不大於該子樹根節點的值。

最小堆恰好相反，

2. 保持堆的性質MAX-HEAPIFY

輸入為一個數組A和下標，當MAX-HEAPIFY被調用時，我們假設的兩棵二叉樹都是最大值，但可能小於，這樣就違反了最大堆性質，因此需要讓下降，以使得以為根的子樹成為最大堆。

def max_heapify(A, i): """ 保持堆的屬性 A: list of ints i: index of node to examine """ l = left(i) r = right(i) if l < len(A) and A[l] > A[i]: largest = l else: largest = i if r < len(A) and A[r] > A[largest]: largest = r if largest != i: A[i],A[largest] = A[largest],A[i] max_heapify(A,largest)if __name__ == __main__: A=[1,2,3,4,5] max_heapify(A,0) print A輸出結果為：[3, 2, 1, 4, 5]

這裡需要注意一點：

在檢查的時候只需要switch ，然後沿著被switch的節點為根的子樹進行遞歸檢查，另一個子樹不需要檢查，因為這裡取得是largest

例如下圖中，對進行check，，因此進行switch，然後沿著的子節點進行遞歸，，然後再進行switch，直到碰到葉子節點。

3. 建堆

首先給出一個問題並進行證明：當用數組表示存儲了n個元素的堆時，葉子節點的下標是

證明：在heap的數組表示中，所有的非葉子節點都在葉子節點之前進行存儲。

如果非葉子節點的數量多於，那麼最後一個非葉子節點的右子節點就會超過heap的邊界，數組下標會大於，因此非葉子節點的下標最多是，也就是所有的父節點下標為 .

同時，節點的父節點是，父節點不可能是葉子節點，因此不可能是葉子節點。

由此我們可以確定，為非葉子節點，而為葉子節點。證畢。

接下來我們說明，給定一個不明順序的數組表示的堆，如何構造最大堆？

def build_max_head(A): i = len(A) / 2 - 1 while i >= 0: max_heapify(A, i) i -= 1if __name__ == __main__: A=[1,2,3,4,5] build_max_head(A) print A輸出結果為：[5, 4, 3, 1, 2]這個結果大家可以自行推導

如上所述，對所有的非葉子節點，自下往上地調用MAX-HEAPIFY，始終維持著子樹的最大堆屬性，因此到根節點，整個樹就成為最大堆。

4. 堆排序演算法HEAP-SORT

基於堆我們如何進行排序呢？

def head_sort(A): result = [] build_max_head(A) while len(A) > 1: result.append(A[0]) A[0],A[len(A)-1] = A[len(A)-1],A[0] A = A[:-1] max_heapify(A,0) result.extend(A) return resultif __name__ == __main__: A=[1,2,3,4,5,7,8,10,400] result = head_sort(A) print result輸出結果為：[400, 10, 8, 7, 5, 4, 3, 2, 1]