From 115c62de8de3b1549453f93b738c4899c72d176a Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Wed, 2 Sep 2009 12:54:38 -0700 Subject: [PATCH] heap algorithm R=rsc DELTA=196 (194 added, 0 deleted, 2 changed) OCL=34234 CL=34263 --- src/pkg/Make.deps | 5 +- src/pkg/Makefile | 1 + src/pkg/container/heap/Makefile | 11 ++++ src/pkg/container/heap/heap.go | 82 ++++++++++++++++++++++++ src/pkg/container/heap/heap_test.go | 99 +++++++++++++++++++++++++++++ 5 files changed, 196 insertions(+), 2 deletions(-) create mode 100644 src/pkg/container/heap/Makefile create mode 100644 src/pkg/container/heap/heap.go create mode 100644 src/pkg/container/heap/heap_test.go diff --git a/src/pkg/Make.deps b/src/pkg/Make.deps index 38e3dd621d..bae5765645 100644 --- a/src/pkg/Make.deps +++ b/src/pkg/Make.deps @@ -3,10 +3,11 @@ base64.install: bytes.install io.install os.install strconv.install big.install: bignum.install: fmt.install bufio.install: io.install os.install strconv.install utf8.install -bytes.install: os.install utf8.install +bytes.install: os.install unicode.install utf8.install compress/flate.install: bufio.install io.install os.install strconv.install compress/gzip.install: bufio.install compress/flate.install hash.install hash/crc32.install io.install os.install compress/zlib.install: bufio.install compress/flate.install hash.install hash/adler32.install io.install os.install +container/heap.install: sort.install container/list.install: container/ring.install: container/vector.install: @@ -53,7 +54,7 @@ rpc.install: bufio.install fmt.install gob.install http.install io.install log.i runtime.install: sort.install: strconv.install: bytes.install math.install os.install unicode.install utf8.install -strings.install: utf8.install +strings.install: unicode.install utf8.install sync.install: syscall.install: sync.install tabwriter.install: bytes.install container/vector.install io.install os.install utf8.install diff --git a/src/pkg/Makefile b/src/pkg/Makefile index 7d0b76e115..73dde239b9 100644 --- a/src/pkg/Makefile +++ b/src/pkg/Makefile @@ -21,6 +21,7 @@ DIRS=\ compress/flate\ compress/gzip\ compress/zlib\ + container/heap\ container/list\ container/ring\ container/vector\ diff --git a/src/pkg/container/heap/Makefile b/src/pkg/container/heap/Makefile new file mode 100644 index 0000000000..2625d19ca4 --- /dev/null +++ b/src/pkg/container/heap/Makefile @@ -0,0 +1,11 @@ +# Copyright 2009 The Go Authors. All rights reserved. +# Use of this source code is governed by a BSD-style +# license that can be found in the LICENSE file. + +include $(GOROOT)/src/Make.$(GOARCH) + +TARG=container/heap +GOFILES=\ + heap.go\ + +include $(GOROOT)/src/Make.pkg diff --git a/src/pkg/container/heap/heap.go b/src/pkg/container/heap/heap.go new file mode 100644 index 0000000000..d35f4d1335 --- /dev/null +++ b/src/pkg/container/heap/heap.go @@ -0,0 +1,82 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// This package provides heap operations for any type that implements +// HeapInterface. +// +package heap + +import "sort" + +// Any type that implements HeapInterface may be used as a +// heap with the following invariants (established after Init +// has been called): +// +// h.Less(i, j) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len() +// +type HeapInterface interface { + sort.SortInterface; + Push(x interface{}); + Pop() interface{}; +} + + +// A heaper must be initialized before any of the heap operations +// can be used. Init is idempotent with respect to the heap invariants +// and may be called whenever the heap invariants may have been invalidated. +// Its complexity is O(n*log(n)) where n = h.Len(). +// +func Init(h HeapInterface) { + sort.Sort(h); +} + + +// Push pushes the element x onto the heap. The complexity is +// O(log(n)) where n = h.Len(). +// +func Push(h HeapInterface, x interface{}) { + h.Push(x); + up(h, h.Len()-1); +} + + +// Pop removes the minimum element (according to Less) from the heap +// and returns it. The complexity is O(log(n)) where n = h.Len(). +// +func Pop(h HeapInterface) interface{} { + n := h.Len()-1; + h.Swap(0, n); + down(h, 0, n); + return h.Pop(); +} + + +func up(h HeapInterface, j int) { + for { + i := (j-1)/2; + if i == j || h.Less(i, j) { + break; + } + h.Swap(i, j); + j = i; + } +} + + +func down(h HeapInterface, i, n int) { + for { + j := 2*i + 1; + if j >= n { + break; + } + if j1 := j+1; j1 < n && !h.Less(j, j1) { + j = j1; // = 2*i + 2 + } + if h.Less(i, j) { + break; + } + h.Swap(i, j); + i = j; + } +} diff --git a/src/pkg/container/heap/heap_test.go b/src/pkg/container/heap/heap_test.go new file mode 100644 index 0000000000..99722f2e9b --- /dev/null +++ b/src/pkg/container/heap/heap_test.go @@ -0,0 +1,99 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package heap + +import ( + "testing"; + "container/vector"; +) + + +type myHeap struct { + vector.IntVector; +} + + +func newHeap() *myHeap { + var h myHeap; + h.IntVector.Init(0); + return &h; +} + + +func (h *myHeap) verify(t *testing.T, i int) { + n := h.Len(); + j1 := 2*i + 1; + j2 := 2*i + 2; + if j1 < n { + if h.Less(j1, i) { + t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j1)); + return; + } + h.verify(t, j1); + } + if j2 < n { + if h.Less(j2, i) { + t.Errorf("heap invariant invalidated [%d] = %d > [%d] = %d", i, h.At(i), j1, h.At(j2)); + return; + } + h.verify(t, j2); + } +} + + +func (h *myHeap) Push(x interface{}) { + h.IntVector.Push(x.(int)); +} + + +func (h *myHeap) Pop() interface{} { + return h.IntVector.Pop(); +} + + +func TestInit(t *testing.T) { + h := newHeap(); + for i := 20; i > 0; i-- { + h.Push(i); + } + Init(h); + h.verify(t, 0); + + for i := 1; h.Len() > 0; i++ { + x := Pop(h).(int); + h.verify(t, 0); + if x != i { + t.Errorf("%d.th pop got %d; want %d", i, x, i); + } + } +} + + +func Test(t *testing.T) { + h := newHeap(); + h.verify(t, 0); + + for i := 20; i > 10; i-- { + h.Push(i); + } + Init(h); + h.verify(t, 0); + + for i := 10; i > 0; i-- { + Push(h, i); + h.verify(t, 0); + } + + for i := 1; h.Len() > 0; i++ { + x := Pop(h).(int); + if i < 20 { + Push(h, 20+i); + } + h.verify(t, 0); + if x != i { + t.Errorf("%d.th pop got %d; want %d", i, x, i); + } + } +} -- 2.48.1