Heap(堆積)其實是一個Complete Binary Tree(完全二元樹). Go的Heap特性是 各個節點都自己是其子樹的根, 且值是最小的. 同個根節點的左子樹的值會小於右子樹. 所以根節點的值是最小的, 位於索引0的位置. 也有另一種是最大的(max heap), 只是Go這裡是最小的(min heap). 定義 : n個元素 k1, k2,…ki…kn, 並且若且唯若滿足下列關係時稱為heap ki <= k2i, ki <= k(2i+1) 或者 ki >= k2i, ki >= k(2i+1), i = 1,2,3…,n/2 又因為最小(或最大)的值, 取出該值都只要O(1)的時間.
通常該結構是用來實現(priority queue)優先隊列的方法之一. 能對任務工作作優先等級的排序用. 底層還是以陣列形式表示
Dijkstra’s algorithm也是能用Heap做實現.
Heap Interface 這裡會提到接口interface, 之後會更詳細的介紹interface的部份
只要實現這些接口, 就可以操作heap提供的各種方法了. 可以看得出來heap接口繼承了sort.Interface, 而sort.Interface內又有三個方法需要實現. 繼承後面會有更詳細的部份介紹. 總之就是要實現這5個方法就行了.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 type Interface interface { sort.Interface Push(x interface {}) Pop() interface {} } type Interface interface { Len() int Less(i, j int ) bool Swap(i, j int ) }
初始化Heap 1 heap.Init(customizeHeap)
Heap內建的操作方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 func Init (h Interface) { n := h.Len() for i := n/2 - 1 ; i >= 0 ; i-- { down(h, i, n) } } func Push (h Interface, x interface {}) { h.Push(x) up(h, h.Len()-1 ) } func Pop (h Interface) interface {} { n := h.Len() - 1 h.Swap(0 , n) down(h, 0 , n) return h.Pop() } func Fix (h Interface, i int ) { if !down(h, i, h.Len()) { up(h, i) } } func Remove (h Interface, i int ) interface {} { n := h.Len() - 1 if n != i { h.Swap(i, n) if !down(h, i, n) { up(h, i) } } return h.Pop() } func down (h Interface, i0, n int ) bool {...}func up (h Interface, j int ) {...}
實現自定義的int Heap 首先定義一個類型或是結構, 並且實現那5個方法. 取官網的範例 來說明
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package mainimport ( "container/heap" "fmt" ) 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 {}) { *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 } func main () { h := &IntHeap{2 , 1 , 5 } heap.Init(h) heap.Push(h, 3 ) heap.Push(h, 4 ) heap.Push(h, 9 ) fmt.Printf("minimum: %d\n" , (*h)[0 ]) for h.Len() > 0 { fmt.Printf("%d " , heap.Pop(h)) } (*h)[1 ] = 6 heap.Fix(h, 1 ) for h.Len() > 0 { fmt.Printf("%d " , heap.Pop(h)) } }
實現Priority Queue 官網範例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 package mainimport ( "container/heap" "fmt" ) type Item struct { value string priority int index int } type PriorityQueue []*Itemfunc (pq PriorityQueue) Len () int { return len (pq) }func (pq PriorityQueue) Less (i, j int ) bool { return pq[i].priority > pq[j].priority } func (pq PriorityQueue) Swap (i, j int ) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PriorityQueue) Push (x interface {}) { n := len (*pq) item := x.(*Item) item.index = n *pq = append (*pq, item) } func (pq *PriorityQueue) Pop () interface {} { old := *pq n := len (old) item := old[n-1 ] old[n-1 ] = nil item.index = -1 *pq = old[0 : n-1 ] return item } func (pq *PriorityQueue) update (item *Item, value string , priority int ) { item.value = value item.priority = priority heap.Fix(pq, item.index) } func main () { items := map [string ]int { "banana" : 3 , "apple" : 2 , "pear" : 4 , } pq := make (PriorityQueue, len (items)) i := 0 for value, priority := range items { pq[i] = &Item{ value: value, priority: priority, index: i, } i++ } heap.Init(&pq) item := &Item{ value: "orange" , priority: 1 , } heap.Push(&pq, item) pq.update(item, item.value, 5 ) for pq.Len() > 0 { item := heap.Pop(&pq).(*Item) fmt.Printf("%.2d:%s " , item.priority, item.value) } }
初始化完成時的heap跟Array
新增orange, 並修改優先權後, 明顯orange被上升到合適的位置了
依序Pop出來
我發現Array位置沒改對…原諒我, 懶得修圖了 - .- 但二元樹是對的!’LeetCode 23 可以嘗試用heap來實現 小弟我日後補上
鐵人賽連結