Golang三叉堆

Golang三叉堆

目录

• 1. 版权
• 2. 概述
• 3.
• 4. 测试
• 5. 测试结果
• 6. 附录
• • container/heap 的down方法
  • 计算大数

1. 版权

本文为原创, 遵循 CC 4.0 BY-SA 版权协议, 转载需注明出处: .
文中代码属于 public domain (无版权).

2. 概述

Golang 里的堆(参见container/heap 源码) 提供了堆的操作. 堆中每个节点只有2个子节点(即二叉树), 父节点<=子节点. 节点修改后, 如>最小子节点, 或小于父节点, 则与之互换位置, 如此一层层处理.

层数和每层处理的时间决定了堆的性能. 如果将堆变成三叉树, 性能会否提升呢?

三叉堆:

// 0
// 1      2      3
// 4 5 6  7 8 9  10 11 12
// 13

• 子节点下标 = 3*父节点下标 + 1,2或3
• 父节点下标 = (子节点下标-1) / 3
• 第i(0,1,…) 层有3**i 个节点: 1,3,9,27,81,243,729,…
• 第i 层之前共有(3**i-1)/2 个节点: 0,1,4,13,40,121,364,…

3.

将三叉堆命名为c-heap. 类似Golang heap, 定义接口:

type Interface interface {sort.InterfacePush(x interface{}) // appendPop() interface{}   // remove last
}

新节点从底部加入, 然后上浮. 删除头部(即最小)节点时先将尾部节点交换上去后执行下沉, 然后删除现在尾部的原头部节点. 数据(例如数组) 想要获得堆功能, 只需实现此接口即可.

最大末父节点:

var pMaxCheap int = pMaxOfCheap() // 最大末父节点下标func pMaxOfCheap() int {var i uint = 0return int((i-1)/2-1-1) / 3 // (最大下标-1) / 3. int最大值=(i-1)/2.
}

第i 层之前共有(3**i-1)/2 个节点.
----
int32
2_147_483_647=int32最大值=数组最大长度.
2_147_483_646=数组最大下标.
1_743_392_200=(3**20-1)/2.
5_230_176_601=(3**21-1)/2.
最大末节点在第20层, 最大末父父节点在第19层.
3x+1<=2_147_483_646, x<=(2_147_483_646-1)/3=715_827_881 - 即最大末父节点下标(3*881+1=2644 - 可以有3个子节点).
----
int64
9_223_372_036_854_775_807=int64最大值=数组最大长度.
9_223_372_036_854_775_806=数组最大下标.
6_078_832_729_528_464_400=(3**40-1)/2.
最大末节点在第40层, 最大末父节点在第39层.
3x+1<=9_223_372_036_854_775_806, x<=(9_223_372_036_854_775_806-1)/3=3_074_457_345_618_258_601 - 即最大末父节点下标(3*601+1=1804 - 可以有3个子节点).

公开方法:

func Init(h Interface) {// heapifyn := h.Len()for i := (n - 1 - 1) / 3; i >= 0; i-- { /* 从末父节点开始. */down(h, i, n)}
}func Push(h Interface, x interface{}) {h.Push(x)up(h, h.Len()-1)
}func Pop(h Interface) interface{} {n := h.Len() - 1h.Swap(0, n)down(h, 0, n)return h.Pop()
}func Remove(h Interface, i int) interface{} {n := h.Len() - 1if n != i {h.Swap(i, n)if !down(h, i, n) {up(h, i)}}return h.Pop()
}func Fix(h Interface, i int) {if !down(h, i, h.Len()) {up(h, i)}
}

上浮操作:

func up(h Interface, j int) {for {i := (j - 1) / 3 // parentif i == j || !h.Less(j, i) {break}h.Swap(i, j)j = i}
}

就是逐层与父比较, 如果小就交换.

下沉操作:

func down(h Interface, i0, n int) bool {i := i0for {if i <= pMaxCheap { // 小于或等于最大末父节点时, 可以有3个子节点(int32/int64 经计算均满足)jc := 3*i + 1if jc >= n {break}jmin := jcjc++ // 子2if jc < n {if h.Less(jc, jmin) {jmin = jc}jc++ // 子3if jc < n && h.Less(jc, jmin) {jmin = jc}}if !h.Less(jmin, i) {break}h.Swap(i, jmin)i = jmin} else { // 超过最大末父节点: 不会有子节点break}}return i > i0
}

就是逐层与最小子比较, 如果大就交换, 但子要<n.

4. 测试

type IntHeap []intfunc (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }func (h *IntHeap) Push(x interface{}) {*h = append(*h, x.(int))
}func (h *IntHeap) Pop() interface{} {old := *hn := len(old)x := old[n-1]*h = old[0 : n-1]return x
}

IntHeap 实现Interface 接口.

首先测试初始化的时间:

// cheap
func main() {rand.Seed(time.Now().Unix())n := 100_000h := IntHeap{}for i := 0; i < n; i++ {h = append(h, rand.Int())}t0 := time.Now()Init(&h)println("init", n, time.Now().Sub(t0).String())// debug(h, len(h))...
}func debug(h []int, n int) {
lo:for i, j := 0, 1; i < n; i++ {fmt.Printf("[%d] %d => ", i, h[i])for k := 0; k < 3; k++ {if j >= n {break lo} else {fmt.Printf("%d ", h[j])j++}}fmt.Println()}fmt.Println()
}

其次单线程持续修改头节点20秒:

	chX := make(chan int)go func() {time.Sleep(20 * time.Second)chX <- 0}()var cnt int64 = 0
lo:for {select {case <-chX:break lodefault:h[0] = rand.Int()Fix(&h, 0)cnt++}}fmt.Printf("stress 20s %d(%d)n", cnt, len(strconv.FormatInt(cnt, 10)))

对比使用Golang heap 的测试(代码类似, 只是改用container/heap):

// heap
func main() {rand.Seed(time.Now().Unix())n := 100_000h := IntHeap{}for i := 0; i < n; i++ {h = append(h, rand.Int())}t0 := time.Now()heap.Init(&h)println("init", n, time.Now().Sub(t0).String())// debug(h, len(h))chX := make(chan int)go func() {time.Sleep(20 * time.Second)chX <- 0}()var cnt int64 = 0
lo:for {select {case <-chX:break lodefault:h[0] = rand.Int()heap.Fix(&h, 0)cnt++}}fmt.Printf("stress 20s %d(%d)n", cnt, len(strconv.FormatInt(cnt, 10)))
}

5. 测试结果

//        数据量   init   stress   内存   CPU
// heap   10w      2.7ms  41kw    4.8M   31%
//        100w     29ms   35kw    35M    31%
//        1kw      297ms  6.3kw   270M   31%
// cheap  10w      1.6ms  37kw    4.8M   31%
//        100w     18ms   32kw    28M    31%
//        1kw      195ms  7.3kw   270M   31%

结论: 三叉堆反而性能略有下降 (init 快是因为Init 方法是从末父节点往前处理, 而三叉堆的叶子节点数肯定多于二叉堆的).

至少从测试的数据量来看, 虽然层数减少, 但由于每层down操作要多1次Less比较, 所以性能反而下降.

另注意, (如果优化)不要试图将3个子节点排序, 因为堂兄弟节点(子节点的子节点) 之间不能保证顺序.

6. 附录

container/heap 的down方法

二叉堆:

// 0
// 1    2
// 3 4  5 6
// 7

第i 层之前共有2**i-1 个节点.
----
int32
2_147_483_647=int32最大值=2**31-1.
2_147_483_646=数组最大下标.
最大末节点在第30层的末尾.
最大末父节点在第29层的末尾.
(注: 二叉堆正好对应二进制数. int32 扣除一个比特的符号位后还有31层, 即第0~30层. 所以最大末节点、最大末父节点分别在第30和29层的末尾.)
----
int64
9_223_372_036_854_775_807=int64最大值=2**63-1.
最大末节点在第62层的末尾.
最大末父节点在第61层的末尾.

down方法:

func down(h Interface, i0, n int) bool {i := i0for {j1 := 2*i + 1if j1 >= n || j1 < 0 { // j1 < 0 after int overflowbreak}j := j1 // left childif j2 := j1 + 1; j2 < n && h.Less(j2, j1) {j = j2 // = 2*i + 2  // right child}...

一旦j1 < 0, 说明i == 最大末父节点 + 1. 最大末父节点本身可以有2个子节点.

计算大数

使用math/big.

	z := big.NewInt(3)// (3**21-1) / 2println(z.Exp(z, big.NewInt(21), nil).Sub(z, big.NewInt(1)).Div(z, big.NewInt(2)).String())