blob: b607e2cbc1c9207e058d1466b92ca536571ce704 (
plain)
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
|
package queue
import (
"codeberg.org/snonux/algorithms/ds"
)
type HeapPriority struct {
ElementaryPriority
}
func NewHeapPriority(capacity int) *HeapPriority {
q := HeapPriority{
ElementaryPriority: ElementaryPriority{make(ds.ArrayList, 0, capacity), capacity},
}
// Index 0 unused
q.a = append(q.a, 0)
return &q
}
func (q *HeapPriority) Empty() bool {
return q.Size() == 0
}
func (q *HeapPriority) Size() int {
return len(q.a) - 1
}
func (q *HeapPriority) Insert(a int) {
q.a = append(q.a, a)
q.swim(len(q.a) - 1)
}
func (q *HeapPriority) Max() (max int) {
if q.Empty() {
return 0
}
return q.a[1]
}
func (q *HeapPriority) DeleteMax() int {
switch q.Size() {
case 0:
return 0
case 1:
max := q.a[1]
q.a = q.a[0:1]
return max
default:
a := q.a[1]
// Last index
max := len(q.a) - 1
q.a.Swap(1, max)
q.a = q.a[0:max]
q.sink(1)
return a
}
}
func (q *HeapPriority) swim(k int) {
for k > 1 && q.a[k/2] < q.a[k] {
q.a.Swap(k/2, k)
k = k / 2
}
}
func (q *HeapPriority) sink(k int) {
// Last index
max := len(q.a) - 1
for 2*k <= max {
// Left child
j := 2 * k
// Go to right child?
if j < max && q.a[j] < q.a[j+1] {
j++
}
// Found my spot in the heap
if q.a[k] >= q.a[j] {
break
}
q.a.Swap(k, j)
k = j
}
}
|
