[TOC] ## heap 堆 > 堆使用的数据结构是最小二叉树，即根节点比左边子树和右边子树的所有值都小。 ``` type Interface func Init(h Interface) func Push(h Interface, x interface{}) func Pop(h Interface) interface{} func Remove(h Interface, i int) interface{} func Fix(h Interface, i int) ``` ## 实例 ### 初始化 help ``` 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{}) { //限制为整数 if n, ok := x.(int); ok { *h = append(*h, n) } } 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) fmt.Println(h) // &[1 2 5 3] // pop 推出最小的元素 heap.Pop(h) fmt.Println(h) // &[2 3 5] heap.Pop(h) fmt.Println(h) // &[3 5] } ``` ### 含优先级的堆 ``` type Item struct { value string priority int // 项的优先级队列 index int } type PriorityQueue []*Item func (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] item.index = -1 // for safety *pq = old[0 : n-1] return item } // 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 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) // 插入新值,并跟新 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) } // Output: // 05:orange 04:pear 03:banana 02:apple } ```