go的heap實(shí)現(xiàn)了堆，關(guān)于堆可以看下數(shù)據(jù)結(jié)構(gòu)：堆（Heap），這里就不闡述了，go實(shí)現(xiàn)的源碼在container/heap/heap.go中，其中包含了1個(gè)接口，5個(gè)外部方法和2個(gè)內(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，需要自己實(shí)現(xiàn)heap.Interface接口，并不是開箱即用的，除了Less方法，其他的都能根據(jù)方法名推出功能，Less方法返回bool類型，典型的實(shí)現(xiàn)就是兩個(gè)元素的比較，通過更改比較規(guī)則，我們可以很方便的實(shí)現(xiàn)最大堆和最小堆

內(nèi)部方法

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

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

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

外部方法

// 初始化堆，構(gòu)建完全二叉樹
func Init(h Interface) {
    // heapify
    n := h.Len()
    // 倒序從第一個(gè)非葉子節(jié)點(diǎn)開始遍歷，如果只有根節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)，則不會(huì)執(zhí)行，不滿足 i >= 0
    // 為什么n/2 - 1是倒序第一個(gè)非葉子節(jié)點(diǎn)呢？
    // 還記得嗎，堆是以完全二叉樹為邏輯結(jié)構(gòu)的
    // 那么假設(shè)有x個(gè)非葉子節(jié)點(diǎn)(x > 1)，那么節(jié)點(diǎn)總數(shù)有兩種情況
    // 一種是最后一個(gè)非葉子節(jié)點(diǎn)有兩個(gè)兒子節(jié)點(diǎn)，即2*x+1 (這個(gè)1是根節(jié)點(diǎn)自己)
    // 另外一個(gè)情況是最后一個(gè)非葉子節(jié)點(diǎn)只有一個(gè)兒子節(jié)點(diǎn)，即(x-1)*2+1+1 = 2*x
    // 因?yàn)閚 = 2*x+1 或者 n = 2*x，所以x = n/2，又因?yàn)檫@里使用的是索引下標(biāo)，所以n/2-1是倒序第一個(gè)非葉子節(jié)點(diǎn)
    // 倒序保證每一個(gè)非葉子節(jié)點(diǎn)作為根節(jié)點(diǎn)的樹都是最大/小堆，以此類推到根節(jié)點(diǎn)，就能保證整個(gè)樹就是最大/最小堆 
    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方法進(jìn)行了初始化
    // 這里默認(rèn)添加入的元素是在尾部，所以自定義的Push方法需要注意下，別跟棧一樣從頂部push
    // 因?yàn)橐呀?jīng)是最大/最小堆了，所以只需要調(diào)用up方法，針對(duì)最末尾的節(jié)點(diǎn)進(jìn)行向上追溯即可 
    up(h, h.Len()-1)
}

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

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

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

舉個(gè)栗子

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