LEFT | RIGHT |
(no file at all) | |
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" |
11 ) | 11 ) |
12 | 12 |
13 // An Item is something we manage in a priority queue. | 13 // An Item is something we manage in a priority queue. |
14 type Item struct { | 14 type Item struct { |
15 value string // The value of the item; arbitrary. | 15 value string // The value of the item; arbitrary. |
16 priority int // The priority of the item in the queue. | 16 priority int // The priority of the item in the queue. |
17 » // The index is needed by changePriority and is maintained by the heap.I
nterface methods. | 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. | 18 index int // The index of the item in the heap. |
19 } | 19 } |
20 | 20 |
21 // A PriorityQueue implements heap.Interface and holds Items. | 21 // A PriorityQueue implements heap.Interface and holds Items. |
22 type PriorityQueue []*Item | 22 type PriorityQueue []*Item |
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. |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
86 pq.update(item, item.value, 5) | 86 pq.update(item, item.value, 5) |
87 | 87 |
88 // Take the items out; they arrive in decreasing priority order. | 88 // Take the items out; they arrive in decreasing priority order. |
89 for pq.Len() > 0 { | 89 for pq.Len() > 0 { |
90 item := heap.Pop(pq).(*Item) | 90 item := heap.Pop(pq).(*Item) |
91 fmt.Printf("%.2d:%s ", item.priority, item.value) | 91 fmt.Printf("%.2d:%s ", item.priority, item.value) |
92 } | 92 } |
93 // Output: | 93 // Output: |
94 // 05:orange 04:pear 03:banana 02:apple | 94 // 05:orange 04:pear 03:banana 02:apple |
95 } | 95 } |
LEFT | RIGHT |