forked from theodesp/go-heaps
-
Notifications
You must be signed in to change notification settings - Fork 0
/
heap.go
64 lines (56 loc) · 1.05 KB
/
heap.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
package go_heaps
// Interface is basic interface that all Heaps implement.
type Interface interface {
// Inserts an element to the heap and returns it
Insert(v Item) Item
// DeleteMin deletes and returns the smallest element
DeleteMin() Item
// FindMin returns the minimum element
FindMin() Item
// Removes all items
Clear()
}
// Item is the basic element that is inserted in a heap
type Item interface {
// Should return a number:
// negative , if a < b
// zero , if a == b
// positive , if a > b
Compare(than Item) int
}
type String string
type Integer int
func (a String) Compare(b Item) int {
s1 := a
s2 := b.(String)
min := len(s2)
if len(s1) < len(s2) {
min = len(s1)
}
diff := 0
for i := 0; i < min && diff == 0; i++ {
diff = int(s1[i]) - int(s2[i])
}
if diff == 0 {
diff = len(s1) - len(s2)
}
if diff < 0 {
return -1
}
if diff > 0 {
return 1
}
return 0
}
func (a Integer) Compare(b Item) int {
a1 := a
a2 := b.(Integer)
switch {
case a1 > a2:
return 1
case a1 < a2:
return -1
default:
return 0
}
}