손 훑 기 golang 기본 데이터 구조 및 알고리즘 더미
발단
최근 에 < > ([일] 석 다 보 휘, 미 야자 키 수 일) 시 리 즈 를 읽 고 골 랑 으로 연습 할 예정 입 니 다.
쌓다
,
“ ”(priority queues)。
,
,
。
: 。
<> 【 】 ;
지식 을 보충 하 다
목표.
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)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.