손 훑 기 golang 기본 데이터 구조 및 알고리즘 더미

10542 단어
손 훑 기 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<= 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, "
    ") } 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)

    좋은 웹페이지 즐겨찾기