-
Notifications
You must be signed in to change notification settings - Fork 3.4k
/
heap.go
72 lines (62 loc) · 1.22 KB
/
heap.go
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
package sketch
import (
"container/heap"
)
type node struct {
event string
count uint32
// used for the container heap Fix function
index uint16
sketchPositions []uint32
}
type MinHeap []*node
func (h MinHeap) Len() int {
return len(h)
}
// less is only used in the underlying pop implementation
func (h MinHeap) Less(i, j int) bool {
return h[i].count < h[j].count
}
func (h MinHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
h[i].index = uint16(i)
h[j].index = uint16(j)
}
func (h *MinHeap) Push(x interface{}) {
n := len(*h)
item := x.(*node)
item.index = uint16(n)
*h = append(*h, item)
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
item := old[n-1]
old[n-1] = nil
item.index = 0
*h = old[0 : n-1]
return item
}
func (h *MinHeap) Peek() interface{} {
return (*h)[0]
}
// update modifies the count and value of an Item in the queue.
func (h *MinHeap) update(event string, count uint32) {
updateNode := -1
for i, k := range *h {
if k.event == event {
k.count = count
updateNode = i
break
}
}
heap.Fix(h, updateNode)
}
func (h *MinHeap) Find(e string) (int, bool) {
for i := 0; i < len(*h); i++ {
if (*h)[i].event == e {
return i, true
}
}
return 0, false
}