1 // Copyright 2012 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // This example demonstrates a priority queue built using the heap interface. 6 package heap_test 7 8 import ( 9 "container/heap" 10 "fmt" 11 ) 12 13 // An Item is something we manage in a priority queue. 14 type Item struct { 15 value string // The value of the item; arbitrary. 16 priority int // The priority of the item in the queue. 17 // The index is needed by update and is maintained by the heap.Interface methods. 18 index int // The index of the item in the heap. 19 } 20 21 // A PriorityQueue implements heap.Interface and holds Items. 22 type PriorityQueue []*Item 23 24 func (pq PriorityQueue) Len() int { return len(pq) } 25 26 func (pq PriorityQueue) Less(i, j int) bool { 27 // We want Pop to give us the highest, not lowest, priority so we use greater than here. 28 return pq[i].priority > pq[j].priority 29 } 30 31 func (pq PriorityQueue) Swap(i, j int) { 32 pq[i], pq[j] = pq[j], pq[i] 33 pq[i].index = i 34 pq[j].index = j 35 } 36 37 func (pq *PriorityQueue) Push(x interface{}) { 38 n := len(*pq) 39 item := x.(*Item) 40 item.index = n 41 *pq = append(*pq, item) 42 } 43 44 func (pq *PriorityQueue) Pop() interface{} { 45 old := *pq 46 n := len(old) 47 item := old[n-1] 48 item.index = -1 // for safety 49 *pq = old[0 : n-1] 50 return item 51 } 52 53 // update modifies the priority and value of an Item in the queue. 54 func (pq *PriorityQueue) update(item *Item, value string, priority int) { 55 item.value = value 56 item.priority = priority 57 heap.Fix(pq, item.index) 58 } 59 60 // This example creates a PriorityQueue with some items, adds and manipulates an item, 61 // and then removes the items in priority order. 62 func Example_priorityQueue() { 63 // Some items and their priorities. 64 items := map[string]int{ 65 "banana": 3, "apple": 2, "pear": 4, 66 } 67 68 // Create a priority queue, put the items in it, and 69 // establish the priority queue (heap) invariants. 70 pq := make(PriorityQueue, len(items)) 71 i := 0 72 for value, priority := range items { 73 pq[i] = &Item{ 74 value: value, 75 priority: priority, 76 index: i, 77 } 78 i++ 79 } 80 heap.Init(&pq) 81 82 // Insert a new item and then modify its priority. 83 item := &Item{ 84 value: "orange", 85 priority: 1, 86 } 87 heap.Push(&pq, item) 88 pq.update(item, item.value, 5) 89 90 // Take the items out; they arrive in decreasing priority order. 91 for pq.Len() > 0 { 92 item := heap.Pop(&pq).(*Item) 93 fmt.Printf("%.2d:%s ", item.priority, item.value) 94 } 95 // Output: 96 // 05:orange 04:pear 03:banana 02:apple 97 } 98
