二叉堆的性質
1.二叉堆是一顆完全二叉樹，最后一層的葉子從左到右排列，其它的每一層都是滿的
2.最小堆父結點小于等于其每一個子結點的鍵值，最大堆則相反
3.每個結點的左子樹或者右子樹都是一個二叉堆
下面是一個最小堆：
堆的存儲
通常堆是通過一維數組來實現的。在起始數組為 0 的情形中：
1.父節點i的左子節點在位置 (2*i+1);
2.父節點i的右子節點在位置 (2*i+2);
3.子節點i的父節點在位置 floor((i-1)/2);
維持堆的性質
我們以最大堆來介紹（后續會分別給出最大堆和最小堆的實現）.所謂維持堆得性質就是字面意思，也就是確保葉子節點和父節點的關系是堆得關系； 那么怎么維持呢？
這里我們是以某一個節點為起始點，調整其自身與子節點的關系，使得父節點總是大于子節點，處理完畢后遞歸操作調整后的節點；
我們來看一下具體的實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/*** 維護最大堆的性質*/func heapify(inout A:[Int], i:Int, size:Int) { var l = 2 * i var r = l + 1 var largest = i if l < size && A[l] > A[i] { largest = l } if r < size && A[r] > A[largest] { largest = r } if largest != i { swap(&A, i, largest) heapify(&A, largest, size) } } |
有效代碼也就10行上下， 簡單解釋下，根據傳入的節點在數組內的索引，計算出左右子節點，然后比較比較子節點的值大小，將大的值對調為父節點的值，最后遞歸處理新節點；
構建堆
現在來看第二步，也就是構建一個堆。我們的輸入數據源是一個以為數組，需要通過構建，將其以堆的性質加以調整； 我們來看一下具體的實現：
|
1
2
3
4
5
6
7
8
9
|
/*** 構建最大堆*/func buildHeap(inout A:[Int]) { for var i = A.count/2; i >= 0; i-- { heapify(&A, i, A.count) } println("build heap:\(A)")} |
簡單解釋下，根據上一步已經得到的維護堆性質的函數，我們隊數組內的所有非葉子節點遍歷，針對每個節點都做一遍堆處理，最后得到的就是一個完整的堆； 可能不理解的騷年會問了，為什么數組遍歷不是全量的，而是[A.count/2, 0]?
這個問題，我想最好的的答案是你畫一個二叉樹，一眼就能明白，這棵樹中非葉子節點的索引就是count/2;
現在重溫一下，這個經典的堆排序是怎么實現的。
以算法導論中對堆排序的介紹，可以簡單的歸結為三句話：
1.維持堆的性質
2.構建堆
3.堆排序
好，終于到了見證奇跡的時刻，我們把數組排個序輸出一下。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
/***堆排序*/func heapSort(inout A:[Int]) { buildHeap(&A) var size = A.count for var i = A.count - 1; i >= 1; i-- { swap(&A, i, 0) size-- heapify(&A, 0, size) } println("sorted heap:\(A)")} |
這里呢，需要注意的地方就是每次得到最大值后，我們需要把問題的解規模減小，因為我們是原址排序，實際上是把一維數組分為了未排序的堆和已排序的數組兩部分，已排序的部分放在數組尾部；
驗證一下
隨便搞個數組，我們排個隊
|
1
2
3
4
5
|
var A = [4, 1, 3, 2, 16, 9,9, 10, 14, 8, 7]heapSort(&A)avens-MacBook-Pro:aven$ ./max-heap-sort.swift build heap:[16, 14, 9, 10, 8, 7, 9, 2, 3, 1, 4]sorted heap:[1, 2, 3, 4, 7, 8, 9, 9, 10, 14, 16] |
小結
上面我們已經完成了最大堆的算法的編碼，最小堆也是類似的； 算法這東西如果能理解的話寫起來就不太難，所以一定要對理論有所了解，真正理解了算法思路才能吧思路寫成代碼。
