简简单单！手撸golang 基本数据结构与算法 堆，不要太崇拜我！

概述缘起最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)本系列笔记拟采用golang练习之堆堆是一种图的树形结构，被用于实现“优先队列”（priorityqueues）。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆中存储数据时必须遵 缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

堆

堆是一种图的树形结构，被用于实现“优先队列”（priority queues）。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按顺序取出。在堆中存储数据时必须遵守这样一条规则：子结点必定大于父结点。摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

补充知识堆又名二叉堆, 是一种无序完全二叉树所谓完全, 是指节点从上至下, 从左至右填充, 中间不会留有空隙完全二叉树可以使用数组存放, 因为其父节点与左右子节点的索引存在线性关系, 以0下标为例 parent.index = (child.index - 1) / 2, 如: 0 = (1 - 1) / 2, 0 = (2 - 1) / 2left.index = parent.index * 2 + 1, 如: 1 = 0 * 2 + 1right.index = left.index + 1 添加数据时 先把数据添加到最末尾, 也就是堆的右下角然后跟父节点比较大小, 如果小于父节点, 则交换之, 又名上浮重复上浮的过程, 直到满足堆的规则: 父节点总是小于子节点 d出数据时 总是d出堆顶, 也就是最小值然后把堆的末尾值, 放到堆顶. 移动末尾值, 不会留下中间间隙, 保持完全二叉树的状态如果堆顶值大于某个子节点的值, 则与最小值节点交换, 又名下沉重复下沉的过程, 直到满足堆的规则: 父节点总是小于子节点 目标基于数组实现二叉堆, 并验证堆排序的功能设计IComparator: 值大小比较器接口. 通过翻转比较函数, 也可以创建最大堆(顶点值最大).IHeap: 定义堆的接口IIterator: 堆迭代器接口tComparator: 值大小比较器, 实现IComparator接口, 具体比较函数由外部传入tArrayHeap: 二叉堆, 实现IHeap接口tHeAPIterator: 堆迭代器, 实现IIterator接口单元测试

heap_test.go, 验证二叉堆的基本功能, 并通过随机Push和有序Pop, 观察堆排序的效果

package data_structureimport (    "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)PASSok      command-line-arguments  0.002s

IComparator.go

值大小比较器接口. 通过翻转比较函数, 也可以创建最大堆(顶点值最大).

package heaptype IComparator interface {    Less(a interface{}, b interface{}) bool}

IHeap.go

定义堆的接口

package heaptype IHeap interface {    Size() int    IsEmpty() bool    IsNotEmpty() bool    Push(value interface{})    Pop() (error, interface{})    Iterator() IIterator    String() string}

IIterator.go

堆迭代器接口

package heaptype IIterator interface {    More() bool    Next() (error,interface{})}

tComparator.go

值大小比较器, 实现IComparator接口, 具体比较函数由外部传入

package heapimport "errors"type FnLess func(a interface{}, b interface{}) booltype 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 heapimport (    "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 heapimport "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")

最后

最后我为大家准备了java核心知识点+全套架构师学习资料和视频+一线大厂面试宝典+面试简历模板+阿里美团网易腾讯小米爱奇艺快手哔哩哔哩面试题+Spring源码合集+Java架构实战电子书一起免费分享给大家！
如果有需要的朋友点击这里备注csdn，自行下载就好了

总结

以上是内存溢出为你收集整理的简简单单！手撸golang 基本数据结构与算法 堆，不要太崇拜我！全部内容，希望文章能够帮你解决简简单单！手撸golang 基本数据结构与算法 堆，不要太崇拜我！所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。