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 heap
import (
"cmp"
"testing"
)
func verify(t *testing.T, h *Heap[int], i int) {
t.Helper()
n := h.Len()
j1 := 2*i + 1
j2 := 2*i + 2
if j1 < n {
if h.compare(h.buf[j1], h.buf[i]) < 0 {
t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.buf[i], j1, h.buf[j1])
return
}
verify(t, h, j1)
}
if j2 < n {
if h.compare(h.buf[j2], h.buf[i]) < 0 {
t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.buf[i], j1, h.buf[j2])
return
}
verify(t, h, j2)
}
}
func Test(t *testing.T) {
t.Parallel()
h := New(cmp.Compare[int])
verify(t, h, 0)
h.Grow(20)
verify(t, h, 0)
for i := 20; i > 10; i-- {
h.Push(i)
}
verify(t, h, 0)
for i := 10; i > 0; i-- {
h.Push(i)
verify(t, h, 0)
}
for i := 1; h.Len() > 0; i++ {
x, ok := h.Pop()
if !ok {
t.Errorf("Pop() = false, want %d", i)
}
if i < 20 {
h.Push(20 + i)
}
verify(t, h, 0)
if x != i {
t.Errorf("%d.th pop got %d; want %d", i, x, i)
}
}
}
func TestPopEmpty(t *testing.T) {
t.Parallel()
h := New(cmp.Compare[int])
_, gotOk := h.Pop()
const want = false
if gotOk != want {
t.Errorf("Pop() on empty heap = %t, want %t", gotOk, want)
}
}
|
