1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
<h1> Package heap </h1> <ul id="short-nav">
<li><code>import "container/heap"</code></li>
<li><a href="#pkg-overview" class="overviewLink">Overview</a></li>
<li><a href="#pkg-index" class="indexLink">Index</a></li>
<li><a href="#pkg-examples" class="examplesLink">Examples</a></li>
</ul> <h2 id="pkg-overview">Overview </h2> <p>Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the minimum-valued node in its subtree. </p>
<p>The minimum element in the tree is the root, at index 0. </p>
<p>A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue. The Examples include such an implementation; the file example_pq_test.go has the complete source. </p> <h4 id="example__intHeap"> <span class="text">Example (IntHeap)</span>
</h4> <p>This example inserts several ints into an IntHeap, checks the minimum, and removes them in order of priority. </p> <p>Code:</p> <pre class="code" data-language="go">// 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) 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 any) {
// 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() any {
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.
func Example_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
}
</pre> <h4 id="example__priorityQueue"> <span class="text">Example (PriorityQueue)</span>
</h4> <p>This example creates a PriorityQueue with some items, adds and manipulates an item, and then removes the items in priority order. </p> <p>Code:</p> <pre class="code" data-language="go">// This example demonstrates a priority queue built using the heap interface.
package heap_test
import (
"container/heap"
"fmt"
)
// 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) Len() int { return len(pq) }
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) 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 any) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() any {
old := *pq
n := len(old)
item := old[n-1]
old[n-1] = nil // avoid memory leak
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)
}
// This example creates a PriorityQueue with some items, adds and manipulates an item,
// and then removes the items in priority order.
func Example_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] = &Item{
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
}
</pre> <h2 id="pkg-index">Index </h2> <ul id="manual-nav">
<li><a href="#Fix">func Fix(h Interface, i int)</a></li>
<li><a href="#Init">func Init(h Interface)</a></li>
<li><a href="#Pop">func Pop(h Interface) any</a></li>
<li><a href="#Push">func Push(h Interface, x any)</a></li>
<li><a href="#Remove">func Remove(h Interface, i int) any</a></li>
<li><a href="#Interface">type Interface</a></li>
</ul> <div id="pkg-examples"> <h3>Examples</h3> <dl> <dd><a class="exampleLink" href="#example__intHeap">Package (IntHeap)</a></dd> <dd><a class="exampleLink" href="#example__priorityQueue">Package (PriorityQueue)</a></dd> </dl> </div> <h3>Package files</h3> <p> <span>heap.go</span> </p> <h2 id="Fix">func <span>Fix</span> <span title="Added in Go 1.2">1.2</span> </h2> <pre data-language="go">func Fix(h Interface, i int)</pre> <p>Fix re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling <a href="#Remove">Remove</a>(h, i) followed by a Push of the new value. The complexity is O(log n) where n = h.Len(). </p>
<h2 id="Init">func <span>Init</span> </h2> <pre data-language="go">func Init(h Interface)</pre> <p>Init establishes the heap invariants required by the other routines in this package. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. The complexity is O(n) where n = h.Len(). </p>
<h2 id="Pop">func <span>Pop</span> </h2> <pre data-language="go">func Pop(h Interface) any</pre> <p>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 <a href="#Remove">Remove</a>(h, 0). </p>
<h2 id="Push">func <span>Push</span> </h2> <pre data-language="go">func Push(h Interface, x any)</pre> <p>Push pushes the element x onto the heap. The complexity is O(log n) where n = h.Len(). </p>
<h2 id="Remove">func <span>Remove</span> </h2> <pre data-language="go">func Remove(h Interface, i int) any</pre> <p>Remove removes and returns the element at index i from the heap. The complexity is O(log n) where n = h.Len(). </p>
<h2 id="Interface">type <span>Interface</span> </h2> <p>The Interface type describes the requirements for a type using the routines in this package. Any type that implements it may be used as a min-heap with the following invariants (established after <a href="#Init">Init</a> has been called or if the data is empty or sorted): </p>
<pre data-language="go">!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
</pre> <p>Note that <a href="#Push">Push</a> and <a href="#Pop">Pop</a> in this interface are for package heap's implementation to call. To add and remove things from the heap, use <a href="#Push">heap.Push</a> and <a href="#Pop">heap.Pop</a>. </p>
<pre data-language="go">type Interface interface {
sort.Interface
Push(x any) // add x as element Len()
Pop() any // remove and return element Len() - 1.
}</pre><div class="_attribution">
<p class="_attribution-p">
© Google, Inc.<br>Licensed under the Creative Commons Attribution License 3.0.<br>
<a href="http://golang.org/pkg/container/heap/" class="_attribution-link">http://golang.org/pkg/container/heap/</a>
</p>
</div>
|
