1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
14 func (h
*myHeap
) Less(i
, j
int) bool {
15 return (*h
)[i
] < (*h
)[j
]
18 func (h
*myHeap
) Swap(i
, j
int) {
19 (*h
)[i
], (*h
)[j
] = (*h
)[j
], (*h
)[i
]
22 func (h
*myHeap
) Len() int {
26 func (h
*myHeap
) Pop() (v
interface{}) {
27 *h
, v
= (*h
)[:h
.Len()-1], (*h
)[h
.Len()-1]
31 func (h
*myHeap
) Push(v
interface{}) {
32 *h
= append(*h
, v
.(int))
35 func (h myHeap
) verify(t
*testing
.T
, i
int) {
42 t
.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i
, h
[i
], j1
, h
[j1
])
49 t
.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i
, h
[i
], j1
, h
[j2
])
56 func TestInit0(t
*testing
.T
) {
58 for i
:= 20; i
> 0; i
-- {
59 h
.Push(0) // all elements are the same
64 for i
:= 1; h
.Len() > 0; i
++ {
68 t
.Errorf("%d.th pop got %d; want %d", i
, x
, 0)
73 func TestInit1(t
*testing
.T
) {
75 for i
:= 20; i
> 0; i
-- {
76 h
.Push(i
) // all elements are different
81 for i
:= 1; h
.Len() > 0; i
++ {
85 t
.Errorf("%d.th pop got %d; want %d", i
, x
, i
)
90 func Test(t
*testing
.T
) {
94 for i
:= 20; i
> 10; i
-- {
100 for i
:= 10; i
> 0; i
-- {
105 for i
:= 1; h
.Len() > 0; i
++ {
112 t
.Errorf("%d.th pop got %d; want %d", i
, x
, i
)
117 func TestRemove0(t
*testing
.T
) {
119 for i
:= 0; i
< 10; i
++ {
126 x
:= Remove(h
, i
).(int)
128 t
.Errorf("Remove(%d) got %d; want %d", i
, x
, i
)
134 func TestRemove1(t
*testing
.T
) {
136 for i
:= 0; i
< 10; i
++ {
141 for i
:= 0; h
.Len() > 0; i
++ {
142 x
:= Remove(h
, 0).(int)
144 t
.Errorf("Remove(0) got %d; want %d", x
, i
)
150 func TestRemove2(t
*testing
.T
) {
154 for i
:= 0; i
< N
; i
++ {
159 m
:= make(map[int]bool)
161 m
[Remove(h
, (h
.Len()-1)/2).(int)] = true
166 t
.Errorf("len(m) = %d; want %d", len(m
), N
)
168 for i
:= 0; i
< len(m
); i
++ {
170 t
.Errorf("m[%d] doesn't exist", i
)
175 func BenchmarkDup(b
*testing
.B
) {
177 h
:= make(myHeap
, 0, n
)
178 for i
:= 0; i
< b
.N
; i
++ {
179 for j
:= 0; j
< n
; j
++ {
180 Push(&h
, 0) // all elements are the same
188 func TestFix(t
*testing
.T
) {
192 for i
:= 200; i
> 0; i
-= 10 {
198 t
.Fatalf("Expected head to be 10, was %d", (*h
)[0])
204 for i
:= 100; i
> 0; i
-- {
205 elem
:= rand
.Intn(h
.Len())