最小 d-堆

发表于 更新于

最近为 timer 撸的
timer repo: https://github.com/vizee/timer

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
const d_ary = 4

func heap_siftup(h []int, i int) {
	v := h[i]
	for i > 0 {
		p := (i - 1) / d_ary
		if h[p] <= v {
			break
		}
		h[i] = h[p]
		i = p
	}
	h[i] = v
}

func heap_siftdown(h []int, i int) {
	v := h[i]
	n := (len(h) + d_ary - 2) / d_ary
	for i < n {
		b := d_ary*i + 1
		min := b
		for j := b + 1; j < b+d_ary && j < len(h); j++ {
			if h[j] < h[min] {
				min = j
			}
		}
		if h[min] >= v {
			break
		}
		h[i] = h[min]
		i = min
	}
	h[i] = v
}

func heap_push(h []int, x int) []int {
	h = append(h, x)
	heap_siftup(h, len(h)-1)
	return h
}

func heap_pop(h []int) ([]int, int) {
	x := h[0]
	h[0] = h[len(h)-1]
	h = h[:len(h)-1]
	if len(h) > 1 {
		heap_siftdown(h, 0)
	}
	return h, x
}