Hand roll Golang basic data structure and algorithm heap

origin

Recently read << my first algorithm book >>([day] Ishida Baohui; This series of notes will be practiced using Golang

The heap

A heap is a tree structure of graphs that are used to implement "priority queues". A priority queue is a data structure in which data can be freely added but retrieved in order from the minimum value. One rule you must follow when storing data in the heap is that the child is always larger than the parent. Excerpt from << my first algorithm book >> [day] shikida bokai; Miyazaki build a

Supplement knowledge

  • A heap, also known as a binary heap, is an unordered complete binary tree
  • Complete means that the nodes are filled from top to bottom and from left to right without gaps

  • A full binary tree can be stored using an array, because the parent node has a linear relationship with the index of the left and right child nodes, as in the case of 0 subscript

    • Parent. Index = (Child. Index – 1) / 2, e.g. 0 = (1-1) / 2, 0 = (2-1) / 2
    • left.index = parent.index 2 + 1, e.g. 1 = 0 2 + 1
    • right.index = left.index + 1

  • When you add data

    • The data is first added to the very end, which is the bottom right corner of the heap
    • Then compare the size with the parent node, if less than the parent node, then swap, also known as floating
    • Repeat the process until the rule of the heap is satisfied: the parent node is always smaller than the child node

  • When the data pops out

    • It always pops up to the top of the heap, which is the minimum
    • And then you put the end of the heap on top of the heap. Move the trailing value, leaving no gap in the middle, and keep the state of the full binary tree
    • If the top value of the heap is greater than the value of a child node, it is swapped with the minimum node, also known as sink
    • Repeat the sinking process until the rule of the heap is satisfied: the parent node is always smaller than the child node

The target

  • Realize binary heap based on array, and verify the function of heap sort

design

  • ICOMParator: The value size comparator interface. By flipping the comparison function, you can also create the maximum heap (maximum vertex value).
  • IHEAP: Defines the interface to the heap
  • Iiterator: Heap iterator interface
  • TComparator: Value-size comparator, which implements the ICOMParator interface. The specific comparison function is passed in externally
  • TARRAYHEAP: Binary heap that implements the IHEAP interface
  • TheApIterator: Heap iterator that implements the Iiterator interface

Unit testing

Heap_test. go, verify the basic function of binary heap, and observe the effect of heap sort by random Push and ordered 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.L og fnAssertTrue (s) (s = = "0,1,2,3,4,5,6,7,8,9", "expecting 0-9")}

Test output

$ 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: 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

Value-size comparator interface. By flipping the comparison function, you can also create the maximum heap (maximum vertex value).

package heap

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

IHeap.go

Define the interface of the heap

package heap

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

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

    Iterator() IIterator
    String() string
}

IIterator.go

Heap iterator interface

package heap

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

tComparator.go

Value size comparator, to achieve ICOMParator interface, the specific comparison function from the external incoming

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

Binary heap to achieve the IHEAP interface

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

Heap iterator, which implements the Iiterator interface

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)