go的heap實現(xiàn)了堆，關(guān)于堆可以看下數(shù)據(jù)結(jié)構(gòu)：堆（Heap），這里就不闡述了，go實現(xiàn)的源碼在container/heap/heap.go中，其中包含了1個接口，5個外部方法和2個內(nèi)部方法

接口

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

// 其中sort.Interface的定義如下
type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

也就是說，要使用heap，需要自己實現(xiàn)heap.Interface接口，并不是開箱即用的，除了Less方法，其他的都能根據(jù)方法名推出功能，Less方法返回bool類型，典型的實現(xiàn)就是兩個元素的比較，通過更改比較規(guī)則，我們可以很方便的實現(xiàn)最大堆和最小堆

內(nèi)部方法

// 這是個典型的堆向下追溯的過程
func down(h Interface, i0, n int) bool {
    i := i0
    for {
        // 先找左節(jié)點，如果左節(jié)點不存在，那右節(jié)點更不可能存在了，直接break跳出即可
        j1 := 2*i + 1
        if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
            break
        }
        j := j1 // left child
        // 再找右節(jié)點，滿足右節(jié)點存在且跟左節(jié)點比較符合自定義的Less方法的預(yù)期，即返回true，就讓右節(jié)點去跟父節(jié)點比較
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
            j = j2 // = 2*i + 2  // right child
        }
        // 假設(shè)這里是找最小堆
        // min(左節(jié)點, 右節(jié)點) 再跟父節(jié)點比較，如果比父節(jié)點大，那就不用調(diào)換，直接退出即可
        if !h.Less(j, i) {
            break
        }
        // 調(diào)換父節(jié)點和min(左節(jié)點, 右節(jié)點)
        h.Swap(i, j)
        // 一旦發(fā)生了調(diào)換，那么肯定有某個子節(jié)點發(fā)生了變更，需要以該字節(jié)為父節(jié)點，重復(fù)上述操作直到未發(fā)生調(diào)換行為或者追溯到了葉子節(jié)點
        i = j
    }
    // 只要發(fā)生調(diào)換，那么i就不會再等于i0，這里是通過這個來標記整個追溯過程是否發(fā)生了父子節(jié)點的調(diào)換 
    return i > i0
}

// 堆向上追溯的過程
func up(h Interface, j int) {
    for {
        // 找到j(luò)對應(yīng)節(jié)點的父節(jié)點，下面簡稱為j節(jié)點
        i := (j - 1) / 2 // parent
        // 如果j節(jié)點就是根節(jié)點或者j節(jié)點和父節(jié)點不滿足Less方法的預(yù)期，即返回false，不用進行調(diào)換，直接退出即可
        if i == j || !h.Less(j, i) {
            break
        }
        // 調(diào)換j節(jié)點和父節(jié)點
        h.Swap(i, j)
        // 同樣的一旦發(fā)生了調(diào)換，那么父節(jié)點肯定就發(fā)生了變更，需要以父節(jié)點作為子節(jié)點，重復(fù)上訴操作直到未發(fā)生調(diào)換行為或者追溯到了根節(jié)點
        j = i
    }
}

down和up，根據(jù)自定義的Less和Swap方法進行比較和調(diào)換，一個實現(xiàn)向下追溯，一個實現(xiàn)向上追溯，最終目的是為了保證每一個父節(jié)點、左子節(jié)點和右子節(jié)點的三元組滿足 父節(jié)點 <=/>= min/max(左子節(jié)點，右子節(jié)點)

外部方法

// 初始化堆，構(gòu)建完全二叉樹
func Init(h Interface) {
    // heapify
    n := h.Len()
    // 倒序從第一個非葉子節(jié)點開始遍歷，如果只有根節(jié)點一個節(jié)點，則不會執(zhí)行，不滿足 i >= 0
    // 為什么n/2 - 1是倒序第一個非葉子節(jié)點呢？
    // 還記得嗎，堆是以完全二叉樹為邏輯結(jié)構(gòu)的
    // 那么假設(shè)有x個非葉子節(jié)點(x > 1)，那么節(jié)點總數(shù)有兩種情況
    // 一種是最后一個非葉子節(jié)點有兩個兒子節(jié)點，即2*x+1 (這個1是根節(jié)點自己)
    // 另外一個情況是最后一個非葉子節(jié)點只有一個兒子節(jié)點，即(x-1)*2+1+1 = 2*x
    // 因為n = 2*x+1 或者 n = 2*x，所以x = n/2，又因為這里使用的是索引下標，所以n/2-1是倒序第一個非葉子節(jié)點
    // 倒序保證每一個非葉子節(jié)點作為根節(jié)點的樹都是最大/小堆，以此類推到根節(jié)點，就能保證整個樹就是最大/最小堆 
    for i := n/2 - 1; i >= 0; i-- {
        down(h, i, n)
    }
}

// 添加元素
func Push(h Interface, x interface{}) {
    // 自定義方法
    h.Push(x)
    // 注意Push的前提是已經(jīng)調(diào)用了Init方法進行了初始化
    // 這里默認添加入的元素是在尾部，所以自定義的Push方法需要注意下，別跟棧一樣從頂部push
    // 因為已經(jīng)是最大/最小堆了，所以只需要調(diào)用up方法，針對最末尾的節(jié)點進行向上追溯即可 
    up(h, h.Len()-1)
}

// 彈出最大/最小元素
func Pop(h Interface) interface{} {
    // 獲取最末尾元素的索引
    n := h.Len() - 1
    // 將首尾元素調(diào)換，這里首位元素就是最大/最小值，是需要被pop出去的
    h.Swap(0, n)
    // 因為根節(jié)點即首位元素發(fā)生了變化，所以需要調(diào)用down方法進行向下追溯
    // 注意這里的n不是h.Len()，而是h.Len() - 1，因為有pop動作，新的長度會減1
    down(h, 0, n)
    // 這里默認是從尾部彈出，自定義實現(xiàn)的時候需要注意一下，別跟棧一樣從頂部彈出了
    return h.Pop()
}

// 移除某個元素
func Remove(h Interface, i int) interface{} {
    // 獲取最末尾元素的索引
    n := h.Len() - 1
    // 如果移除的元素不是末尾元素
    if n != i {
        // 調(diào)換節(jié)點i和節(jié)點n
        h.Swap(i, n)
        // 調(diào)用down方法進行向下追溯，這里n也是h.Len() - 1，原因同上
        // 如果向下追溯過程中發(fā)生了調(diào)換，就不用再調(diào)用向上追溯了，因為節(jié)點i的子節(jié)點都比節(jié)點i小/大(針對最大堆和最小堆)
        if !down(h, i, n) {
            up(h, i)
        }
    }
    // 彈出末尾元素
    return h.Pop()
}

// 針對某個節(jié)點i，發(fā)起堆修復(fù)操作
// 比如更改了某個節(jié)點的值，就需要重新維護
func Fix(h Interface, i int) {
    // 這里跟Remove方法中的操作基本一樣，就是分別向下向上追溯的過程，不再細說
    if !down(h, i, h.Len()) {
        up(h, i)
    }
}

舉個栗子

源碼分析的差不多了，下面來看下應(yīng)用

type hs []int

func (recv hs) Less(i, j int) bool {
    return recv[i] < recv[j]
}

func (recv hs) Len() int {
    return len(recv)
}

func (recv hs) Swap(i, j int) {
    recv[i], recv[j] = recv[j], recv[i]
}

func (recv *hs) Push(x interface{}) {
    item := x.(int)
    *recv = append(*recv, item)
}

func (recv *hs) Pop() interface{} {
    l := len(*recv) - 1
    item := (*recv)[l]
    *recv = (*recv)[:l]
    return item
}

func main()  {

    var hp hs = []int{4,2,3,7,5,1,5,3,8,9,3,2,0}
    hpPtr := &hp
    fmt.Println(hp.Less(0, 1)) // false
    fmt.Println(hp.Len()) // 13
    hp.Swap(2, 3)
    fmt.Println(hp) // [4 2 7 3 5 1 5 3 8 9 3 2 0]
    hpPtr.Push(11)
    fmt.Println(hp) // [4 2 7 3 5 1 5 3 8 9 3 2 0 11]
    hpPtr.Pop()
    fmt.Println(hp) // [4 2 7 3 5 1 5 3 8 9 3 2 0]

    heap.Init(hpPtr)
    fmt.Println(hp) // [0 2 1 3 3 2 5 3 8 9 5 4 7]
    fmt.Println(heap.Pop(hpPtr)) // 0
    heap.Push(hpPtr, -1) 
    fmt.Println(hp) // [-1 2 1 3 3 2 5 3 8 9 5 7 4]
    heap.Remove(hpPtr, 0)
    fmt.Println(hp) // [1 2 2 3 3 4 5 3 8 9 5 7]
    hp[3] = -1
    fmt.Println(hp) // [1 2 2 -1 3 4 5 3 8 9 5 7]
    heap.Fix(hpPtr, 3)
    fmt.Println(hp) // [-1 1 2 2 3 4 5 3 8 9 5 7]
}

總結(jié)

heap個人感覺是一個工具類的半成品吧，做不到開箱即用，而且使用者需要對heap的實現(xiàn)比較了解，否則可能容易踩坑，比如上面說到的，heap中Pop方法默認彈出末位元素，Less方法如何實現(xiàn)才能控制最大/小堆等等，而且使用其他方法之前必須先調(diào)用Init方法，否則結(jié)果可能是非預(yù)期的，這點heap里面也沒有進行限制，最后建議如果使用heap，最好跟上面例子一樣使用slice進行包裝，這樣接入的成本是最低的