-
Notifications
You must be signed in to change notification settings - Fork 148
/
Copy pathcontainer_heap.htm
206 lines (205 loc) · 11.1 KB
/
container_heap.htm
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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
<!DOCTYPE html>
<html lang="en">
<head profile="http://a9.com/-/spec/opensearch/1.1/">
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link href="../assets/site.css" rel="stylesheet">
<title>container/heap</title>
</head>
<body>
<div class="container">
<h2 id="pkg-overview">package heap</h2>
<p><code>import "container/heap"</code>
<p align="left">heap包提供了对任意类型（实现了heap.Interface接口）的堆操作。（最小）堆是具有“每个节点都是以其为根的子树中最小值”属性的树。</p>
<p align="left">树的最小元素为其根元素，索引0的位置。</p>
<p align="left">heap是常用的实现优先队列的方法。要创建一个优先队列，实现一个具有使用（负的）优先级作为比较的依据的Less方法的Heap接口，如此一来可用Push添加项目而用Pop取出队列最高优先级的项目。</p>
<div class="panel-group">
<div class="panel panel-default" id="example-package--IntHeap">
<div class="panel-heading" onclick="document.getElementById('ex-package--IntHeap').style.display = document.getElementById('ex-package--IntHeap').style.display=='none'?'block':'none';">Example (IntHeap)</div>
<div id="ex-package--IntHeap" class="panel-collapse collapse">
<div class="panel-body">
<pre><span class="com">// This example demonstrates an integer heap built using the heap interface.</span>
package heap_test
import (
"container/heap"
"fmt"
)
<span class="com">// An IntHeap is a min-heap of ints.</span>
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 interface{}) {
<span class="com">// Push and Pop use pointer receivers because they modify the slice's length,</span>
<span class="com">// not just its contents.</span>
*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
}
<span class="com">// This example inserts several ints into an IntHeap, checks the minimum,</span>
<span class="com">// and removes them in order of priority.</span>
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))
}
<span class="com">// Output:</span>
<span class="com">// minimum: 1</span>
<span class="com">// 1 2 3 5</span>
}
</pre>
</div>
</div>
</div>
<div class="panel panel-default" id="example-package--PriorityQueue">
<div class="panel-heading" onclick="document.getElementById('ex-package--PriorityQueue').style.display = document.getElementById('ex-package--PriorityQueue').style.display=='none'?'block':'none';">Example (PriorityQueue)</div>
<div id="ex-package--PriorityQueue" class="panel-collapse collapse">
<div class="panel-body">
<pre><span class="com">// This example demonstrates a priority queue built using the heap interface.</span>
package heap_test
import (
"container/heap"
"fmt"
)
<span class="com">// An Item is something we manage in a priority queue.</span>
type Item struct {
value string <span class="com">// The value of the item; arbitrary.</span>
priority int <span class="com">// The priority of the item in the queue.</span>
<span class="com">// The index is needed by update and is maintained by the heap.Interface methods.</span>
index int <span class="com">// The index of the item in the heap.</span>
}
<span class="com">// A PriorityQueue implements heap.Interface and holds Items.</span>
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
<span class="com">// We want Pop to give us the highest, not lowest, priority so we use greater than here.</span>
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 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]
item.index = -1 <span class="com">// for safety</span>
*pq = old[0 : n-1]
return item
}
<span class="com">// update modifies the priority and value of an Item in the queue.</span>
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
item.value = value
item.priority = priority
heap.Fix(pq, item.index)
}
<span class="com">// This example creates a PriorityQueue with some items, adds and manipulates an item,</span>
<span class="com">// and then removes the items in priority order.</span>
func Example_priorityQueue() {
<span class="com">// Some items and their priorities.</span>
items := map[string]int{
"banana": 3, "apple": 2, "pear": 4,
}
<span class="com">// Create a priority queue, put the items in it, and</span>
<span class="com">// establish the priority queue (heap) invariants.</span>
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)
<span class="com">// Insert a new item and then modify its priority.</span>
item := &Item{
value: "orange",
priority: 1,
}
heap.Push(&pq, item)
pq.update(item, item.value, 5)
<span class="com">// Take the items out; they arrive in decreasing priority order.</span>
for pq.Len() > 0 {
item := heap.Pop(&pq).(*Item)
fmt.Printf("%.2d:%s ", item.priority, item.value)
}
<span class="com">// Output:</span>
<span class="com">// 05:orange 04:pear 03:banana 02:apple</span>
}
</pre>
</div>
</div>
</div>
</div>
<h3 id="pkg-index" class="section-header">Index <a class="permalink" href="#pkg-index">¶</a></h3>
<a href="../main.html"><h3>返回首页</h3></a>
</br>
<li><a href="#Interface">type Interface</a></li>
<li><a href="#Init">func Init(h Interface)</a></li>
<li><a href="#Push">func Push(h Interface, x interface{})</a></li>
<li><a href="#Pop">func Pop(h Interface) interface{}</a></li>
<li><a href="#Remove">func Remove(h Interface, i int) interface{}</a></li>
<li><a href="#Fix">func Fix(h Interface, i int)</a></li>
</ul>
<h4 id="pkg-examples">Examples <a class="permalink" href="#pkg-index">¶</a></h4>
<a href="../main.html"><h3>返回首页</h3></a>
</br>
<li><a href="#example-package--IntHeap" onclick="$('#ex-package--IntHeap').addClass('in').removeClass('collapse').height('auto')">package (IntHeap)</a></li>
<li><a href="#example-package--PriorityQueue" onclick="$('#ex-package--PriorityQueue').addClass('in').removeClass('collapse').height('auto')">package (PriorityQueue)</a></li>
</ul>
<h3 id="Interface">type <a title="View Source" href="https://github.com/golang/go/blob/master/src/container/heap/heap.go?name=release#30">Interface</a> <a class="permalink" href="#pkg-index">¶</a></h3>
<pre>type Interface interface {
<a href="sort.htm">sort</a>.<a href="sort.htm#Interface">Interface</a>
<span id="Interface.Push">Push</span>(x interface{}) <span class="com">// 向末尾添加元素</span>
<span id="Interface.Pop">Pop</span>() interface{} <span class="com">// 从末尾删除元素</span>
}</pre>
<p>任何实现了本接口的类型都可以用于构建最小堆。最小堆可以通过heap.Init建立，数据是递增顺序或者空的话也是最小堆。最小堆的约束条件是：</p>
<pre>!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()
</pre>
<p>注意接口的Push和Pop方法是供heap包调用的，请使用heap.Push和heap.Pop来向一个堆添加或者删除元素。</p>
<h3 id="Init">func <a title="View Source" href="https://github.com/golang/go/blob/master/src/container/heap/heap.go?name=release#41">Init</a> <a class="permalink" href="#pkg-index">¶</a></h3>
<pre class="funcdecl">func Init(h <a href="#Interface">Interface</a>)</pre>
<p>一个堆在使用任何堆操作之前应先初始化。Init函数对于堆的约束性是幂等的（多次执行无意义），并可能在任何时候堆的约束性被破坏时被调用。本函数复杂度为O(n)，其中n等于h.Len()。</p>
<h3 id="Push">func <a title="View Source" href="https://github.com/golang/go/blob/master/src/container/heap/heap.go?name=release#52">Push</a> <a class="permalink" href="#pkg-index">¶</a></h3>
<pre class="funcdecl">func Push(h <a href="#Interface">Interface</a>, x interface{})</pre>
<p>向堆h中插入元素x，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。</p>
<h3 id="Pop">func <a title="View Source" href="https://github.com/golang/go/blob/master/src/container/heap/heap.go?name=release#61">Pop</a> <a class="permalink" href="#pkg-index">¶</a></h3>
<pre class="funcdecl">func Pop(h <a href="#Interface">Interface</a>) interface{}</pre>
<p>删除并返回堆h中的最小元素（不影响约束性）。复杂度O(log(n))，其中n等于h.Len()。等价于Remove(h, 0)。</p>
<h3 id="Remove">func <a title="View Source" href="https://github.com/golang/go/blob/master/src/container/heap/heap.go?name=release#71">Remove</a> <a class="permalink" href="#pkg-index">¶</a></h3>
<pre class="funcdecl">func Remove(h <a href="#Interface">Interface</a>, i <a href="builtin.htm#int">int</a>) interface{}</pre>
<p align="left">删除堆中的第i个元素，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。</p>
<h3 id="Fix">func <a title="View Source" href="https://github.com/golang/go/blob/master/src/container/heap/heap.go?name=release#85">Fix</a> <a class="permalink" href="#pkg-index">¶</a></h3>
<pre class="funcdecl">func Fix(h <a href="#Interface">Interface</a>, i <a href="builtin.htm#int">int</a>)</pre>
<p align="left">在修改第i个元素后，调用本函数修复堆，比删除第i个元素后插入新元素更有效率。</p>
<p align="left">复杂度O(log(n))，其中n等于h.Len()。</p>
</div>
<div id="x-footer" class="clearfix">
<div class="container">
<a href="http://studygolang.com/" target="_blank">Go语言中文网</a>
<span class="text-muted">|</span> <a href="http://golang.org/" target="_blank">Go Language</a>
<span class="pull-right"><a href="#">Back to top</a></span>
</div>
</div>
<script src="../assets/jquery-2.0.3.min.js"></script>
<script src="../assets/bootstrap.min.js"></script>
<script src="../assets/site.js"></script>
</body>
</html>