Left: | ||
Right: |
OLD | NEW |
---|---|
1 // Copyright 2012 The Go Authors. All rights reserved. | 1 // Copyright 2012 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 // This example demonstrates a priority queue built using the heap interface. | 5 // This example demonstrates a priority queue built using the heap interface. |
6 package heap_test | 6 package heap_test |
7 | 7 |
8 import ( | 8 import ( |
9 "container/heap" | 9 "container/heap" |
10 "fmt" | 10 "fmt" |
(...skipping 12 matching lines...) Expand all Loading... | |
23 | 23 |
24 func (pq PriorityQueue) Len() int { return len(pq) } | 24 func (pq PriorityQueue) Len() int { return len(pq) } |
25 | 25 |
26 func (pq PriorityQueue) Less(i, j int) bool { | 26 func (pq PriorityQueue) Less(i, j int) bool { |
27 // We want Pop to give us the highest, not lowest, priority so we use gr eater than here. | 27 // We want Pop to give us the highest, not lowest, priority so we use gr eater than here. |
28 return pq[i].priority > pq[j].priority | 28 return pq[i].priority > pq[j].priority |
29 } | 29 } |
30 | 30 |
31 func (pq PriorityQueue) Swap(i, j int) { | 31 func (pq PriorityQueue) Swap(i, j int) { |
32 pq[i], pq[j] = pq[j], pq[i] | 32 pq[i], pq[j] = pq[j], pq[i] |
33 » pq[i].index = i | 33 » pq[i].index, pq[j].index = i, j |
rsc
2013/01/18 20:08:24
Please restore the old code. This is not a swap.
cespare
2013/01/18 21:00:29
Done.
| |
34 » pq[j].index = j | |
35 } | 34 } |
36 | 35 |
37 func (pq *PriorityQueue) Push(x interface{}) { | 36 func (pq *PriorityQueue) Push(x interface{}) { |
38 // Push and Pop use pointer receivers because they modify the slice's le ngth, | |
39 // not just its contents. | |
40 n := len(*pq) | 37 n := len(*pq) |
41 item := x.(*Item) | 38 item := x.(*Item) |
42 item.index = n | 39 item.index = n |
43 *pq = append(*pq, item) | 40 *pq = append(*pq, item) |
44 } | 41 } |
45 | 42 |
46 func (pq *PriorityQueue) Pop() interface{} { | 43 func (pq *PriorityQueue) Pop() interface{} { |
47 » a := *pq | 44 » old := *pq |
48 » n := len(a) | 45 » n := len(old) |
49 » item := a[n-1] | 46 » item := old[n-1] |
50 item.index = -1 // for safety | 47 item.index = -1 // for safety |
51 » *pq = a[0 : n-1] | 48 » *pq = old[0 : n-1] |
52 return item | 49 return item |
53 } | 50 } |
54 | 51 |
55 // update is not used by the example but shows how to take the top item from | 52 // update modifies the priority and value of an Item in the queue. |
56 // the queue, update its priority and value, and put it back. | 53 func (pq *PriorityQueue) update(item *Item, value string, priority int) { |
57 func (pq *PriorityQueue) update(value string, priority int) { | 54 » heap.Remove(pq, item.index) |
58 » item := heap.Pop(pq).(*Item) | |
59 item.value = value | 55 item.value = value |
60 item.priority = priority | 56 item.priority = priority |
61 heap.Push(pq, item) | 57 heap.Push(pq, item) |
62 } | 58 } |
63 | 59 |
64 // changePriority is not used by the example but shows how to change the | 60 // This example inserts some items into a PriorityQueue, manipulates an item, |
65 // priority of an arbitrary item. | 61 // and then removes the items in priority order. |
66 func (pq *PriorityQueue) changePriority(item *Item, priority int) { | 62 func Example_priorityQueue() { |
67 » heap.Remove(pq, item.index) | 63 » // Some items and their priorities. |
68 » item.priority = priority | 64 » items := map[string]int{ |
65 » » "banana": 3, "apple": 2, "pear": 4, | |
66 » } | |
67 | |
68 » // Create a priority queue and put the items in it. | |
69 » pq := &PriorityQueue{} | |
70 » heap.Init(pq) | |
71 » for value, priority := range items { | |
72 » » item := &Item{ | |
73 » » » value: value, | |
74 » » » priority: priority, | |
75 » » } | |
76 » » heap.Push(pq, item) | |
77 » } | |
78 | |
79 » // Insert a new item and then modify its priority. | |
80 » item := &Item{ | |
81 » » value: "orange", | |
82 » » priority: 1, | |
83 » } | |
69 heap.Push(pq, item) | 84 heap.Push(pq, item) |
70 } | 85 » pq.update(item, item.value, 5) |
71 | 86 |
72 // This example pushes 10 items into a PriorityQueue and takes them out in | 87 » // Take the items out; they arrive in decreasing priority order. |
73 // order of priority. | 88 » for pq.Len() > 0 { |
74 func Example() { | 89 » » item := heap.Pop(pq).(*Item) |
75 » const nItem = 10 | |
76 » // Random priorities for the items (a permutation of 0..9, times 11)). | |
77 » priorities := [nItem]int{ | |
78 » » 77, 22, 44, 55, 11, 88, 33, 99, 00, 66, | |
79 » } | |
80 » values := [nItem]string{ | |
81 » » "zero", "one", "two", "three", "four", "five", "six", "seven", " eight", "nine", | |
82 » } | |
83 » // Create a priority queue and put some items in it. | |
84 » pq := make(PriorityQueue, 0, nItem) | |
85 » for i := 0; i < cap(pq); i++ { | |
86 » » item := &Item{ | |
87 » » » value: values[i], | |
88 » » » priority: priorities[i], | |
89 » » } | |
90 » » heap.Push(&pq, item) | |
91 » } | |
92 » // Take the items out; should arrive in decreasing priority order. | |
93 » // For example, the highest priority (99) is the seventh item, so output starts with 99:"seven". | |
94 » for i := 0; i < nItem; i++ { | |
95 » » item := heap.Pop(&pq).(*Item) | |
96 fmt.Printf("%.2d:%s ", item.priority, item.value) | 90 fmt.Printf("%.2d:%s ", item.priority, item.value) |
97 } | 91 } |
98 // Output: | 92 // Output: |
99 » // 99:seven 88:five 77:zero 66:nine 55:three 44:two 33:six 22:one 11:fou r 00:eight | 93 » // 05:orange 04:pear 03:banana 02:apple |
100 } | 94 } |
OLD | NEW |