如何将完全二叉樹“堆化”？
上篇介紹了幾個概念，這篇我們研究一個問題，就是怎麼把完全二叉樹變成二叉堆，也就是“堆化”？
目前示例：将完全二叉樹轉化成最小堆。
算法分析
首先，我們将目标鎖定在最後一棵子樹上？也就是标号➀區域位置。原因是，如果調整就從最後面調整，然後逐個的延伸到最高層。
如圖所示，調整的順序是➀→➁→➂→➃→➄→...。這個思路是很合理的，也是“堆化”的算法思路。
下面用一個局部片段來示範下過程，假如有下面的一條線：
按照算法，先調整結點6，比較發現比左孩子小，不用動。右孩子沒有，結束。
接着，調整節點7。它有兩個孩子，先比較兩個孩子，4>2。再拿7和較小的2比較，發現大于，是以7和2交換值，得到如下：
接着，調整節點5。它有兩個孩子，先比較孩子，6>2，是以5和2進行交換，得到如下：
但是，交換之後，節點5下還有兩個孩子，是以遞歸再進行比較。這一步我們就知道了，拿5和4進行交換，得到如下：
由于已經到葉子節點，此輪結束。從這一輪操作中，我們就了解了為什麼要從下往上一層層調整的原因。
-------------------
接着，調整節點2，發現左右孩子都比它大，不動。
最後，調整節點1，發現左右孩子都比它大，不動。
整個流程結束。
-------------------
下沉
在上面例子中，将一個節點逐漸向下移動的過程，形象的稱為“下沉”操作（down）。
golang提供的是一個實作了通用最小堆的heap，初始化（Init）操作就是将一個完全二叉樹“堆化”的過程。
func down(h Interface, i0, n int) bool
i := i0
for {
j1 := 2*i + 1
if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
break
}
j := j1 // left child
if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
j = j2 // = 2*i + 2 // right child
}
if !h.Less(j, i) {
break
}
h.Swap(i, j)
i = j
}
return i > i0 down方法就是前文算法過程的實作。
總結
本文詳細介紹了“堆化”的過程，相信聰明的讀者看下就能了解。下篇繼續研究。