了解二叉堆數據構造及Swift的堆排序算法完成示例。本站提示廣大學習愛好者：（了解二叉堆數據構造及Swift的堆排序算法完成示例）文章只能為提供參考，不一定能成為您想要的結果。以下是了解二叉堆數據構造及Swift的堆排序算法完成示例正文
二叉堆的性質
1.二叉堆是一顆完全二叉樹，最後一層的葉子從左到右陳列，其它的每一層都是滿的
2.最小堆父結點小於等於其每一個子結點的鍵值，最大堆則相反
3.每個結點的左子樹或許右子樹都是一個二叉堆
上面是一個最小堆：
堆的存儲
通常堆是經過一維數組來完成的。在起始數組為 0 的情形中：
1.父節點i的左子節點在地位 (2*i+1);
2.父節點i的右子節點在地位 (2*i+2);
3.子節點i的父節點在地位 floor((i-1)/2);
維持堆的性質
我們以最大堆來引見（後續會辨別給出最大堆和最小堆的完成）.所謂維持堆得性質就是字面意思，也就是確保葉子節點和父節點的關系是堆得關系； 那麼怎樣維持呢？
這裡我們是以某一個節點為起始點，調整其本身與子節點的關系，使得父節點總是大於子節點，處置終了後遞歸操作調整後的節點；
我們來看一下詳細的完成：
/**
* 維護最大堆的性質
*/
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行上下， 復雜解釋下，依據傳入的節點在數組內的索引，計算出左右子節點，然後比擬比擬子節點的值大小，將大的值對調為父節點的值，最後遞歸處置新節點；
構建堆
如今來看第二步，也就是構建一個堆。我們的輸出數據源是一個以為數組，需求經過構建，將其以堆的性質加以調整； 我們來看一下詳細的完成：
/**
* 構建最大堆
*/
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.堆排序
好，終於到了見證奇觀的時辰，我們把數組排個序輸入一下。
/**
*堆排序
*/
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)")
}
這裡呢，需求留意的中央就是每次失掉最大值後，我們需求把問題的解規模減小，由於我們是舊址排序，實踐上是把一維數組分為了未排序的堆和已排序的數組兩局部，已排序的局部放在數組尾部；
驗證一下
隨意搞個數組，我們排個隊
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]
小結
下面我們曾經完成了最大堆的算法的編碼，最小堆也是相似的； 算法這東西假如能了解的話寫起來就不太難，所以一定要對實際有所理解，真正了解了算法思緒才干吧思緒寫成代碼。
