type Interface interface { // Len is the number of elements in the collection. Len() int Less(i, j int) bool // Swap swaps the elements with indexes i and j. Swap(i, j int) }
加上堆接口定义的两个方法
1 2
funcPush(h Interface, x interface{}) {} funcPop(h Interface)interface{} {}
// Push pushes the element x onto the heap. // The complexity is O(log n) where n = h.Len(). funcPush(h Interface, x interface{}) { h.Push(x) // h.Push(x)是外层实体的方法，与本方法不相同 up(h, h.Len()-1) }
出堆Pop
堆的Pop操作是先将堆顶元素与最后一个元素交换位置，然后再将交换后的堆顶元素下沉到属于它的位置。
1 2 3 4 5 6 7 8 9
// Pop removes and returns the minimum element (according to Less) from the heap. // The complexity is O(log n) where n = h.Len(). // Pop is equivalent to Remove(h, 0). funcPop(h Interface)interface{} { n := h.Len() - 1 h.Swap(0, n) down(h, 0, n) return h.Pop() // 这里的h.Pop()是用户自己定义的方法，以上部分操作都只负责将堆顶元素放到末尾并使堆保持其规则，最后这一行是用户自己对实体的操作 }
// Remove removes and returns the element at index i from the heap. // The complexity is O(log n) where n = h.Len(). funcRemove(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(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 }
// 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)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. funcExample_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 }
// An Item is something we manage in a priority queue. type Item struct { value string// The value of the item; arbitrary. priority int// The priority of the item in the queue. // The index is needed by update and is maintained by the heap.Interface methods. index int// The index of the item in the heap. }
func(pq PriorityQueue)Less(i,j int)bool { // We want Pop to give us the highest, not lowest, priority so we use greater than here. return pq[i].priority > pq[j].priority }
然后就是经典的Push()和Pop()方法的实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
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// avoid memory leak item.index = -1// for safety *pq = old[:n-1] return item }
// An Item is something we manage in a priority queue. type Item struct { value string// The value of the item; arbitrary. priority int// The priority of the item in the queue. // The index is needed by update and is maintained by the heap.Interface methods. index int// The index of the item in the heap. }
// A PriorityQueue implements heap.Interface and holds Items. type PriorityQueue []*Item
func(pq PriorityQueue)Less(i,j int)bool { // We want Pop to give us the highest, not lowest, priority so we use greater than here. return pq[i].priority > pq[j].priority }
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// avoid memory leak item.index = -1// for safety *pq = old[: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) }
// This example creates a PriorityQueue with some items, adds and manipulates an item, // and then removes the items in priority order. funcExample_priorityQueue() { // Some items and their priorities. items := map[string]int{ "banana": 3, "apple": 2, "pear": 4, } // Create a priority queue, put the items in it, and // establish the priority queue (heap) invariants. pq := make(PriorityQueue,len(items)) i := 0 for value, priority := range items { pq[i] = &Items { value : value, priority : priority, index : i, } i++ } heap.Init(&pq) // Insert a new item and then modify its priority. item := &Item{ value: "orange", priority: 1, } heap.Push(&pq, item) pq.update(item, item.value, 5) // Take the items out; they arrive in decreasing priority order. 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 }
