[TOC] # heap堆 ## 結構 ~~~ type Interface interface { sort.Interface Push(x interface{}) // 向末尾添加元素 Pop() interface{} // 從末尾刪除元素 } ~~~ 任何實現了本接口的類型都可以用于構建最小堆。最小堆可以通過heap.Init建立，數據是遞增順序或者空的話也是最小堆。最小堆的約束條件是： ~~~ !h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len() ~~~ 注意接口的Push和Pop方法是供heap包調用的，請使用heap.Push和heap.Pop來向一個堆添加或者刪除元素 ## 使用 ~~~ package main import ( "container/heap" "fmt" ) type IntHeap []int //我們自定義一個堆需要實現5個接口 //Len(),Less(),Swap()這是繼承自sort.Interface //Push()和Pop()是堆自已的接口 //返回長度 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中 *h = append(*h, x.(int)) } //彈出數據 func (h *IntHeap) Pop() interface{} { old := *h; n := len(old); x := old[n-1]; //讓h指向新的slice *h = old[0: n-1]; //返回最后一個元素 return x; } //打印堆 func (h *IntHeap) PrintHeap() { //元素的索引號 i := 0 //層級的元素個數 levelCount := 1 for i+1 <= h.Len() { fmt.Println((*h)[i: i+levelCount]) i += levelCount if (i + levelCount*2) <= h.Len() { levelCount *= 2 } else { levelCount = h.Len() - i } } } func main() { a := IntHeap{6, 2, 3, 1, 5, 4}; //初始化堆 heap.Init(&a); a.PrintHeap(); //彈出數據，保證每次操作都是規范的堆結構 fmt.Println(heap.Pop(&a)); a.PrintHeap(); fmt.Println(heap.Pop(&a)); a.PrintHeap(); heap.Push(&a, 0); heap.Push(&a, 8); a.PrintHeap(); } ~~~