geov/heap_test.go at master · rapour/geov · GitHub

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
package geov

import (
	"testing"

	"github.com/stretchr/testify/require"
)

type Number int

func (n Number) Value() int {
	return int(n)
}

func TestHeap(t *testing.T) {

	cases := []struct {
		testname    string
		input       []Element[int]
		sorted      []int
		expectedMin Number
	}{
		{
			testname: "first case",
			input:    []Element[int]{Number(1), Number(3), Number(5), Number(0)},
			sorted:   []int{0, 1, 3, 5},

			expectedMin: 0,
		},
		{
			testname:    "second case",
			input:       []Element[int]{Number(11), Number(3), Number(5), Number(10)},
			sorted:      []int{3, 5, 10, 11},
			expectedMin: 3,
		},
	}

	for _, tc := range cases {
		t.Run(tc.testname, func(t *testing.T) {

			h := NewHeap(tc.input)
			h.BuildMinHeap()
			require.Equal(t, tc.expectedMin, h.Min())

		})
	}

	for _, tc := range cases {
		t.Run(tc.testname, func(t *testing.T) {

			h := NewHeap(tc.input)
			h.BuildMinHeap()

			var sorted []int
			for {
				if h.GetSize() == 0 {
					break
				}
				sorted = append(sorted, h.ExtractMin().Value())
			}
			require.Equal(t, tc.sorted, sorted)

		})
	}

}