손 훑 기 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<= 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)