二叉堆的性質(zhì)
1.二叉堆是一顆完全二叉樹(shù)，最后一層的葉子從左到右排列，其它的每一層都是滿的
2.最小堆父結(jié)點(diǎn)小于等于其每一個(gè)子結(jié)點(diǎn)的鍵值，最大堆則相反
3.每個(gè)結(jié)點(diǎn)的左子樹(shù)或者右子樹(shù)都是一個(gè)二叉堆
下面是一個(gè)最小堆：

堆的存儲(chǔ)
通常堆是通過(guò)一維數(shù)組來(lái)實(shí)現(xiàn)的。在起始數(shù)組為 0 的情形中：
1.父節(jié)點(diǎn)i的左子節(jié)點(diǎn)在位置 (2*i+1);
2.父節(jié)點(diǎn)i的右子節(jié)點(diǎn)在位置 (2*i+2);
3.子節(jié)點(diǎn)i的父節(jié)點(diǎn)在位置 floor((i-1)/2);

維持堆的性質(zhì)
我們以最大堆來(lái)介紹（后續(xù)會(huì)分別給出最大堆和最小堆的實(shí)現(xiàn)）.所謂維持堆得性質(zhì)就是字面意思，也就是確保葉子節(jié)點(diǎn)和父節(jié)點(diǎn)的關(guān)系是堆得關(guān)系； 那么怎么維持呢？

這里我們是以某一個(gè)節(jié)點(diǎn)為起始點(diǎn)，調(diào)整其自身與子節(jié)點(diǎn)的關(guān)系，使得父節(jié)點(diǎn)總是大于子節(jié)點(diǎn)，處理完畢后遞歸操作調(diào)整后的節(jié)點(diǎn)；
我們來(lái)看一下具體的實(shí)現(xiàn)：

/**
* 維護(hù)最大堆的性質(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行上下， 簡(jiǎn)單解釋下，根據(jù)傳入的節(jié)點(diǎn)在數(shù)組內(nèi)的索引，計(jì)算出左右子節(jié)點(diǎn)，然后比較比較子節(jié)點(diǎn)的值大小，將大的值對(duì)調(diào)為父節(jié)點(diǎn)的值，最后遞歸處理新節(jié)點(diǎn)；

構(gòu)建堆
現(xiàn)在來(lái)看第二步，也就是構(gòu)建一個(gè)堆。我們的輸入數(shù)據(jù)源是一個(gè)以為數(shù)組，需要通過(guò)構(gòu)建，將其以堆的性質(zhì)加以調(diào)整； 我們來(lái)看一下具體的實(shí)現(xiàn)：

/**
* 構(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)")
}

簡(jiǎn)單解釋下，根據(jù)上一步已經(jīng)得到的維護(hù)堆性質(zhì)的函數(shù)，我們隊(duì)數(shù)組內(nèi)的所有非葉子節(jié)點(diǎn)遍歷，針對(duì)每個(gè)節(jié)點(diǎn)都做一遍堆處理，最后得到的就是一個(gè)完整的堆； 可能不理解的騷年會(huì)問(wèn)了，為什么數(shù)組遍歷不是全量的，而是[A.count/2, 0]?
這個(gè)問(wèn)題，我想最好的的答案是你畫(huà)一個(gè)二叉樹(shù)，一眼就能明白，這棵樹(shù)中非葉子節(jié)點(diǎn)的索引就是count/2;

堆排序

現(xiàn)在重溫一下，這個(gè)經(jīng)典的堆排序是怎么實(shí)現(xiàn)的。
以算法導(dǎo)論中對(duì)堆排序的介紹，可以簡(jiǎn)單的歸結(jié)為三句話：
1.維持堆的性質(zhì)
2.構(gòu)建堆
3.堆排序
好，終于到了見(jiàn)證奇跡的時(shí)刻，我們把數(shù)組排個(gè)序輸出一下。

/**
*堆排序
*/
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)")
}

這里呢，需要注意的地方就是每次得到最大值后，我們需要把問(wèn)題的解規(guī)模減小，因?yàn)槲覀兪窃放判?，?shí)際上是把一維數(shù)組分為了未排序的堆和已排序的數(shù)組兩部分，已排序的部分放在數(shù)組尾部；

驗(yàn)證一下
隨便搞個(gè)數(shù)組，我們排個(gè)隊(duì)

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)完成了最大堆的算法的編碼，最小堆也是類(lèi)似的； 算法這東西如果能理解的話寫(xiě)起來(lái)就不太難，所以一定要對(duì)理論有所了解，真正理解了算法思路才能吧思路寫(xiě)成代碼。

最新評(píng)論