forked from habeanf/yap
-
Notifications
You must be signed in to change notification settings - Fork 21
/
stlheap.go
82 lines (76 loc) · 1.89 KB
/
stlheap.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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package stlheap
import (
"container/heap"
// "log"
)
type Interface interface {
heap.Interface
Copy(i, j int)
Set(i int, x interface{})
Get(i int) interface{}
LessValue(i int, x interface{}) bool
}
func push(h Interface, holeIndex int, x interface{}) {
parent := (holeIndex - 1) / 2
for holeIndex > 0 && h.LessValue(parent, x) {
// log.Println("putting", parent, holeIndex)
h.Copy(parent, holeIndex)
holeIndex = parent
parent = (holeIndex - 1) / 2
}
// log.Println("pushing value at", holeIndex)
h.Set(holeIndex, x)
}
func adjust(h Interface, length int, x interface{}) {
secondChild, holeIndex := 0, 0
// log.Println("length", length)
// log.Println("SecondChild", secondChild)
for secondChild < (length-1)/2 {
secondChild = 2 * (secondChild + 1)
if h.Less(secondChild, secondChild-1) {
secondChild--
}
// log.Println("Set", holeIndex, secondChild)
h.Swap(holeIndex, secondChild)
holeIndex = secondChild
// log.Println("SecondChild", secondChild)
}
// log.Println("After loop", secondChild)
if length&1 == 0 && secondChild == (length-2)/2 {
secondChild = 2 * (secondChild + 1)
// log.Println("Set", holeIndex, secondChild-1)
h.Copy(secondChild-1, holeIndex)
holeIndex = secondChild - 1
}
// log.Println("Last SecondChild", secondChild)
// log.Println("Pushing at", holeIndex)
push(h, holeIndex, x)
}
// func Pop(h Interface) interface{} {
// n := h.Len() - 1
// h.Swap(0, n)
// Adjust(h, n)
// return h.Pop()
// }
func Sort(h Interface) {
for i := h.Len() - 1; i > 0; i-- {
// log.Println(j)
// Pop without reslicing
// i := agenda.Len() - 1
// agenda.Swap(0, i)
cur := h.Get(i)
h.Copy(0, i)
adjust(h, i, cur)
// rlheap.RegularDown(agenda, 0, i)
// rlheap.Down(agenda, 0, i)
// log.Println(agenda.ConfStr())
// j++
}
// for i := h.Len(); i > 1; {
// i--
// i := h.Len() - 1
// // Pop without reslicing
// h.Swap(0, i)
// Adjust(h, i)
// }
}