-
Notifications
You must be signed in to change notification settings - Fork 0
/
priorityqueue.go
78 lines (68 loc) · 1.37 KB
/
priorityqueue.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
73
74
75
76
77
78
package priorityqueue
type PriorityQueue struct {
q []interface{}
size, capacity int
Less func(a, b interface{}) bool
}
func CreatePriorityQueue(n int, less func(a, b interface{}) bool) PriorityQueue {
return PriorityQueue{make([]interface{}, n), 0, n, less}
}
func (pq *PriorityQueue) Push(v interface{}) bool {
if pq.IsFull() {
return false
}
pq.q[pq.size] = v
pq.size++
pq.up(pq.size - 1)
return true
}
func (pq *PriorityQueue) Pop() interface{} {
if pq.IsEmpty() {
return nil
}
top := pq.q[0]
pq.q[0] = pq.q[pq.size-1]
pq.size--
pq.down(0)
return top
}
func (pq *PriorityQueue) Top() interface{} {
return pq.q[0]
}
func (pq *PriorityQueue) IsFull() bool {
return pq.size == pq.capacity
}
func (pq *PriorityQueue) IsEmpty() bool {
return pq.size == 0
}
func (pq *PriorityQueue) up(pos int) {
for pos > 0 {
i := (pos - 1) / 2
if pq.less(i, pos) {
return
}
pq.q[i], pq.q[pos] = pq.q[pos], pq.q[i]
pos = i
}
}
func (pq *PriorityQueue) down(pos int) {
for pos < pq.size {
small, l := pos, 2*pos+1
if l < pq.size && pq.less(l, small) {
small = l
}
r := l + 1
if r < pq.size && pq.less(r, small) {
small = r
}
if small == pos {
return
}
pq.q[pos], pq.q[small] = pq.q[small], pq.q[pos]
pos = small
}
}
func (pq *PriorityQueue) less(i, j int) bool {
a, b := pq.q[i], pq.q[j]
return pq.Less(a, b)
}