二叉堆的性質
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]

小結
上面我們已經完成了最大堆的算法的編碼，最小堆也是類似的； 算法這東西如果能理解的話寫起來就不太難，所以一定要對理論有所了解，真正理解了算法思路才能吧思路寫成代碼。