golang中实现堆

这个代码写的有些工程化,感觉挺不错的

代码

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package main

import "fmt"

type Heap []int

func (h Heap) swap(i, j int) {
h[i], h[j] = h[j], h[i]
}

func (h Heap) less(i, j int) bool {
if h[i] < h[j] {
return true
}
return false
}

func (h Heap) up(i int) {
for {
f := (i - 1) / 2
if h.less(i, f) {
h.swap(i, f)
f = i
} else {
break
}
}
}

func (h *Heap) Push(x int) {
*h = append(*h, x)
h.up(len(*h) - 1)
}

func (h Heap) down(i int) { //务必注意l和r的边界检查
for {
l := i * 2 + 1
if l >= len(h) {
break
}

j := l

if r := l + 1; r < len(h) && h.less(r, l) {
j = r
}

if h.less(j, i) { //这里要判断一下,没必要down就break掉
h.swap(i, j)
i = j
} else {
break
}
}
}

func (h *Heap) Remove(i int) int {
n := len(*h) - 1
h.swap(n, i)
x := (*h)[n]
*h = (*h)[:n]

if f := (i - 1)/2; h.less(i, f) {
h.up(i)
} else {
h.down(i)
}

return x
}

func (h *Heap) Pop() int {
n := len(*h) - 1
h.swap(0, n)

x := (*h)[n]
*h = (*h)[:n]
h.down(0)
return x
}

func (h Heap) Init() {
n := len(h)

for i := n / 2 - 1; i >= 0; i-- {
h.down(i)
}
}

func (h Heap) OutPut() {
tmp := h

res := make([]int, 0)
for len(tmp) != 0 {
res = append(res, tmp.Pop())
}

fmt.Println(res)
}

func main() {
arr := []int{3, 4, 2, 1, 23, 45, 5, 456, 234, 32, 2, 1, 7}
s := make(Heap, 0)
s = append(s, arr...)
s.Init()
s.OutPut()
}

一个细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (h *Heap) Remove(i int) int {
n := len(*h) - 1
h.swap(n, i)
x := (*h)[n]
*h = (*h)[:n]

if f := (i - 1)/2; h.less(i, f) {
h.up(i)
} else {
h.down(i)
}

return x
}

可以看到这里仍然需要判断一下需不需要up,这并不是多余的操作

1
2
3
4
5
6
7
       10
/ \
9 3
/ \ / \
8 5 1 2
/ \
7 6

在这个最大堆中,如果删除1,用6替换1,如果不进行up操作的话,可以发现就不满足堆的性质了。