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