參考
GO語言heap剖析及利用heap實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列
Golang: 詳解container/heap

在Golang sort介紹了sort接口，實(shí)現(xiàn)自定義排序：

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)
}

sort 包 在內(nèi)部實(shí)現(xiàn)了四種基本的排序算法：插入排序（insertionSort）、歸并排序（symMerge）、堆排序（heapSort）和快速排序（quickSort）； sort 包會(huì)依據(jù)實(shí)際數(shù)據(jù)自動(dòng)選擇最優(yōu)的排序算法。

在container包里，專門有一個(gè)heap，實(shí)現(xiàn)了堆排序：

// Note that Push and Pop in this interface are for package heap's
// implementation to call. To add and remove things from the heap,
// use heap.Push and heap.Pop.
type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}

除了sort接口，還要額外實(shí)現(xiàn)一下push,pop

一、官方例子：

// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This example demonstrates an integer heap built using the heap interface.
package heap_test

import (
    "container/heap"
    "fmt"
)

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    // Push and Pop use pointer receivers because they modify the slice's length,
    // not just its contents.
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func Example_intHeap() {
    h := &IntHeap{2, 1, 5}
    heap.Init(h)
    heap.Push(h, 3)
    fmt.Printf("minimum: %d\n", (*h)[0])
    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
    // Output:
    // minimum: 1
    // 1 2 3 5
}

二、源碼

1.Init

func Init(h Interface) {
    // heapify
    n := h.Len()
    for i := n/2 - 1; i >= 0; i-- {
        down(h, i, n)
    }
}

其實(shí)init之后，就排好序了。關(guān)于堆排序算法，可以參考排序算法(五) 堆排序(選擇排序的進(jìn)化)，在heap.go中也能看到類似的邏輯：

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函數(shù)的功能非常簡(jiǎn)單：給定類型，需要down（下沉）的元素在數(shù)組中的索引，heap的長度，將該元素下沉到該元素對(duì)應(yīng)的子樹合適的位置，從而滿足該子樹為最小堆的要求。

還記得前面的那張順序數(shù)組表示堆的圖嗎？結(jié)合down函數(shù)的實(shí)現(xiàn)：任選一個(gè)元素 i ，將其與它的子節(jié)點(diǎn) 2i+1 和 2i+2比較，如果元素 i 比它的子節(jié)點(diǎn)小，則將元素 i 與兩個(gè)子節(jié)點(diǎn)中較小的節(jié)點(diǎn)交換（j），從而保證滿足最小樹的要求（第一次down）；子節(jié)點(diǎn) j 可能也有它的子節(jié)點(diǎn)，繼續(xù)比較、交換，直到數(shù)組末尾，或者元素 i 比它的兩個(gè)子節(jié)點(diǎn)都小，跳出循環(huán)（）。

為什么元素 i 比它的兩個(gè)子節(jié)點(diǎn)都小，就可以跳出循環(huán)，不再繼續(xù)下去呢？這是由于，在Init函數(shù)中，第一個(gè)開始down（下沉）的元素是第 n/2 - 1 個(gè)，可以保證總是從最后一棵子樹開始down（如前圖，n=8或者n=9, n/2-1總是為4），因此可以保證Init->down時(shí)，如果元素 i 比它的兩個(gè)子節(jié)點(diǎn)都小，那么該元素對(duì)應(yīng)的子樹，就是最小堆。

Init在遍歷完畢后，可以保證，待Init的數(shù)組是一個(gè)最小堆。

2.Fix

func Fix(h Interface, i int)，在修改第i個(gè)元素后，調(diào)用本函數(shù)修復(fù)堆，比刪除第i個(gè)元素后插入新元素更有效率。復(fù)雜度O(log(n))，其中n等于h.Len()。
舉個(gè)例子：

//更新queue中一個(gè)Item的Priority和value, 
//將Item調(diào)整到queue中適當(dāng)?shù)奈恢?滿足堆的特征)
// update modifies the Priority and Value of an Item in the queue.
func (pq *PriorityQueue) Update(item *Item, value string, priority int) {
    item.Value = value
    item.Priority = priority

    // Fix操作比 先Remove再Push要快
    heap.Fix(pq, item.Index)
}