手撸 golang 根本数据结构与算法 堆
缘起
最近浏览 << 我的第一本算法书 >>(【日】石田保辉;宫崎修一)
本系列笔记拟采纳 golang 练习之
堆
堆是一种图的树形构造,被用于实现“优先队列”(priority queues)。优先队列是一种数据结构,能够自在增加数据,但取出数据时要从最小值开始按程序取出。在堆中存储数据时必须恪守这样一条规定:子结点必然大于父结点。摘自 << 我的第一本算法书 >>【日】石田保辉;宫崎修一
补充常识
- 堆又名二叉堆, 是一种无序齐全二叉树
- 所谓齐全, 是指节点从上至下, 从左至右填充, 两头不会留有空隙
-
齐全二叉树能够应用数组寄存, 因为其父节点与左右子节点的索引存在线性关系, 以 0 下标为例
- parent.index = (child.index – 1) / 2, 如: 0 = (1 – 1) / 2, 0 = (2 – 1) / 2
- left.index = parent.index 2 + 1, 如: 1 = 0 2 + 1
- right.index = left.index + 1
-
增加数据时
- 先把数据增加到最开端, 也就是堆的右下角
- 而后跟父节点比拟大小, 如果小于父节点, 则替换之, 又名上浮
- 反复上浮的过程, 直到满足堆的规定: 父节点总是小于子节点
-
弹出数据时
- 总是弹出堆顶, 也就是最小值
- 而后把堆的开端值, 放到堆顶. 挪动开端值, 不会留下两头间隙, 放弃齐全二叉树的状态
- 如果堆顶值大于某个子节点的值, 则与最小值节点替换, 又名下沉
- 反复下沉的过程, 直到满足堆的规定: 父节点总是小于子节点
指标
- 基于数组实现二叉堆, 并验证堆排序的性能
设计
- IComparator: 值大小比拟器接口. 通过翻转比拟函数, 也能够创立最大堆 (顶点值最大).
- IHeap: 定义堆的接口
- IIterator: 堆迭代器接口
- tComparator: 值大小比拟器, 实现 IComparator 接口, 具体比拟函数由内部传入
- tArrayHeap: 二叉堆, 实现 IHeap 接口
- tHeapIterator: 堆迭代器, 实现 IIterator 接口
单元测试
heap_test.go, 验证二叉堆的基本功能, 并通过随机 Push 和有序 Pop, 察看堆排序的成果
package data_structure
import (
"fmt"
"learning/gooop/data_structure/heap"
"math/rand"
"strings"
"testing"
"time"
)
func Test_Heap(t *testing.T) {fnAssertTrue := func(b bool, msg string) {
if !b {panic(msg)
}
}
fnLess := func(a interface{}, b interface{}) bool {i1 := a.(int)
i2 := b.(int)
return i1 < i2
}
comparator := heap.NewComparator(fnLess)
// test empty heap
hp := heap.NewArrayHeap(comparator)
fnAssertTrue(hp.Size() == 0, "expecting size == 0")
fnAssertTrue(hp.IsEmpty(), "expecting empty")
fnAssertTrue(hp.Iterator().More() == false, "expecting !more")
e,_ := hp.Pop()
fnAssertTrue(e != nil, "expecting e != nil")
// push random samples
rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
samples := 13
for i := 0;i < samples;i++ {hp.Push(rnd.Intn(100))
}
t.Log(hp)
// test iterator
iter := hp.Iterator()
itemStrings := make([]string, 0)
for i := 0;i < samples;i++ {e, v := iter.Next()
fnAssertTrue(e == nil, "expecting e == nil")
itemStrings = append(itemStrings, fmt.Sprintf("%v", v))
}
fnAssertTrue(iter.More() == false, "expecting !more")
e,_ = iter.Next()
fnAssertTrue(e != nil, "expecting e != nil")
t.Log(strings.Join(itemStrings, ","))
// test heap sort
prev := -1
size := hp.Size()
for i := 0;i < size;i++ {e,v := hp.Pop()
fnAssertTrue(e == nil, "expecting e == nil")
n := v.(int)
t.Logf("%d = %d", i, n)
if prev >= 0 {fnAssertTrue(prev <= n, "expecting prev <= n")
prev = n
}
prev = n
}
fnAssertTrue(hp.IsEmpty(), "expecting empty")
// test 0-9
for i := 0;i < 10;i++ {hp.Push(i)
}
itemStrings = make([]string, 0)
for ;hp.IsNotEmpty(); {e,v := hp.Pop()
fnAssertTrue(e == nil, "expecting e == nil")
itemStrings = append(itemStrings, fmt.Sprintf("%v", v))
}
s := strings.Join(itemStrings, ",")
t.Log(s)
fnAssertTrue(s == "0,1,2,3,4,5,6,7,8,9", "expecting 0-9")
}
测试输入
$ go test -v heap_test.go
=== RUN Test_Heap
heap_test.go:41:
0
12, 36
36, 17, 37, 53
69, 37, 79, 22, 69, 37
heap_test.go:54: 0,12,36,36,17,37,53,69,37,79,22,69,37
heap_test.go:64: 0 = 0
heap_test.go:64: 1 = 12
heap_test.go:64: 2 = 17
heap_test.go:64: 3 = 22
heap_test.go:64: 4 = 36
heap_test.go:64: 5 = 36
heap_test.go:64: 6 = 37
heap_test.go:64: 7 = 37
heap_test.go:64: 8 = 37
heap_test.go:64: 9 = 53
heap_test.go:64: 10 = 69
heap_test.go:64: 11 = 69
heap_test.go:64: 12 = 79
heap_test.go:84: 0,1,2,3,4,5,6,7,8,9
--- PASS: Test_Heap (0.00s)
PASS
ok command-line-arguments 0.002s
IComparator.go
值大小比拟器接口. 通过翻转比拟函数, 也能够创立最大堆 (顶点值最大).
package heap
type IComparator interface {Less(a interface{}, b interface{}) bool
}
IHeap.go
定义堆的接口
package heap
type IHeap interface {Size() int
IsEmpty() bool
IsNotEmpty() bool
Push(value interface{})
Pop() (error, interface{})
Iterator() IIterator
String() string}
IIterator.go
堆迭代器接口
package heap
type IIterator interface {More() bool
Next() (error,interface{})
}
tComparator.go
值大小比拟器, 实现 IComparator 接口, 具体比拟函数由内部传入
package heap
import "errors"
type FnLess func(a interface{}, b interface{}) bool
type tComparator struct {fnLess FnLess}
func NewComparator(fn FnLess) IComparator {
if fn == nil {panic(gNullArgumentError)
}
return &tComparator{fnLess: fn,}
}
func (me *tComparator) Less(a interface{}, b interface{}) bool {
if a == nil || b == nil {panic(gNullArgumentError)
}
return me.fnLess(a, b)
}
var gNullArgumentError = errors.New("null argument error")
tArrayHeap.go
二叉堆, 实现 IHeap 接口
package heap
import (
"errors"
"fmt"
"strings"
)
type tArrayHeap struct {
comparator IComparator
items []interface{}
size int
version int64
}
func NewArrayHeap(comparator IComparator) IHeap {
return &tArrayHeap{
comparator: comparator,
items: make([]interface{}, 0),
size: 0,
version: 0,
}
}
func (me *tArrayHeap) Size() int {return me.size}
func (me *tArrayHeap) IsEmpty() bool {return me.size <= 0}
func (me *tArrayHeap) IsNotEmpty() bool {return !me.IsEmpty()
}
func (me *tArrayHeap) Push(value interface{}) {
me.version++
me.ensureSize(me.size + 1)
me.items[me.size] = value
me.size++
me.shiftUp(me.size - 1)
me.version++
}
func (me *tArrayHeap) ensureSize(size int) {for ;len(me.items) < size; {me.items = append(me.items, nil)
}
}
func (me *tArrayHeap) parentOf(i int) int {return (i - 1) / 2
}
func (me *tArrayHeap) leftChildOf(i int) int {return i*2 + 1}
func (me *tArrayHeap) rightChildOf(i int) int {return me.leftChildOf(i) + 1
}
func (me *tArrayHeap) last() (i int, v interface{}) {if me.IsEmpty() {return -1, nil}
i = me.size - 1
v = me.items[i]
return i,v
}
func (me *tArrayHeap) shiftUp(i int) {
if i <= 0 {return}
v := me.items[i]
pi := me.parentOf(i)
pv := me.items[pi]
if me.comparator.Less(v, pv) {me.items[pi], me.items[i] = v, pv
me.shiftUp(pi)
}
}
func (me *tArrayHeap) Pop() (error, interface{}) {if me.IsEmpty() {return gNoMoreElementsError, nil}
me.version++
top := me.items[0]
li, lv := me.last()
me.items[0] = nil
me.size--
if me.IsEmpty() {return nil, top}
me.items[0] = lv
me.items[li] = nil
me.shiftDown(0)
me.version++
return nil, top
}
func (me *tArrayHeap) shiftDown(i int) {pv := me.items[i]
ok, ci, cv := me.minChildOf(i)
if ok && me.comparator.Less(cv, pv) {me.items[i], me.items[ci] = cv, pv
me.shiftDown(ci)
}
}
func (me *tArrayHeap) minChildOf(p int) (ok bool, i int, v interface{}) {li := me.leftChildOf(p)
if li >= me.size {return false, 0, nil}
lv := me.items[li]
ri := me.rightChildOf(p)
if ri >= me.size {return true, li, lv}
rv := me.items[ri]
if me.comparator.Less(lv, rv) {return true, li, lv} else {return true, ri, rv}
}
func (me *tArrayHeap) Iterator() IIterator {return newHeapIterator(me)
}
func (me *tArrayHeap) String() string {
level := 0
lines := make([]string, 0)
lines = append(lines, "")
for {
n := 1<<level
min := n - 1
max := n + min - 1
if min >= me.size {break}
line := make([]string, 0)
for i := min;i <= max;i++ {
if i >= me.size {break}
line = append(line, fmt.Sprintf("%4d", me.items[i]))
}
lines = append(lines, strings.Join(line, ","))
level++
}
return strings.Join(lines, "\n")
}
var gNoMoreElementsError = errors.New("no more elements")
tHeapIterator.go
堆迭代器, 实现 IIterator 接口
package heap
import "errors"
type tHeapIterator struct {
heap *tArrayHeap
pos int
version int64
}
func newHeapIterator(heap *tArrayHeap) IIterator {
return &tHeapIterator{
heap: heap,
pos: 0,
version: heap.version,
}
}
func (me *tHeapIterator) More() bool {
if me.version != me.heap.version {return false}
return me.pos < me.heap.size
}
func (me *tHeapIterator) Next() (error, interface{}) {
if me.version != me.heap.version {return gConcurrentModificationError, nil}
if me.pos >= me.heap.size {return gNoMoreElementsError, nil}
v := me.heap.items[me.pos]
me.pos++
return nil, v
}
var gConcurrentModificationError = errors.New("concurrent modification error")
(end)