关于算法:手撸golang-基本数据结构与算法-堆

2次阅读

共计 6546 个字符，预计需要花费 17 分钟才能阅读完成。

最近浏览 << 我的第一本算法书 >>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳 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

值大小比拟器接口. 通过翻转比拟函数, 也能够创立最大堆 (顶点值最大).

package heap

type IComparator interface {Less(a interface{}, b interface{}) bool
}

定义堆的接口

package heap

type IHeap interface {Size() int
    IsEmpty() bool
    IsNotEmpty() bool

    Push(value interface{})
    Pop() (error, interface{})

    Iterator() IIterator
    String() string}

堆迭代器接口

package heap

type IIterator interface {More() bool
    Next() (error,interface{})
}

值大小比拟器, 实现 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")

二叉堆, 实现 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")

堆迭代器, 实现 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)

正文完

算法

发表至：算法

2021-02-19

0

关于算法:嘿Jina-帮我画一幅高山流水图

关于算法:拓端tecdatR语言中如何使用排队论预测等待时间

关于算法:机器学习实战系列一工业蒸汽量预测最新版本下篇含特征优化模型融合等

关于算法:ELEX-4618面向对象设计

关于css:前端面试每日-31-第675天

关于算法:手撸golang-基本数据结构与算法-堆

手撸 golang 根本数据结构与算法堆

缘起

堆

补充常识

指标

设计

单元测试

测试输入

IComparator.go

IHeap.go

IIterator.go

tComparator.go

tArrayHeap.go

tHeapIterator.go

站内搜索

关于算法:手撸golang-基本数据结构与算法-堆

手撸 golang 根本数据结构与算法 堆

缘起

堆

补充常识

指标

设计

单元测试

测试输入

IComparator.go

IHeap.go

IIterator.go

tComparator.go

tArrayHeap.go

tHeapIterator.go

站内搜索

手撸 golang 根本数据结构与算法堆