summaryrefslogtreecommitdiff
path: root/queue
diff options
context:
space:
mode:
authorPaul Buetow <paul@buetow.org>2020-10-16 09:23:27 +0100
committerPaul Buetow <paul@buetow.org>2020-10-16 09:23:27 +0100
commit2f700943480cf9767bf5090feeac626af742c1c8 (patch)
tree313b7b795b3a84aaef92c4b39c174167b9aa95ea /queue
parentda8837c515cbefadce9bdbb5e035398f89b283ec (diff)
migrate to gomodules
Diffstat (limited to 'queue')
-rw-r--r--queue/elementarypriority.go2
-rw-r--r--queue/heappriority.go18
-rw-r--r--queue/queue_test.go3
3 files changed, 12 insertions, 11 deletions
diff --git a/queue/elementarypriority.go b/queue/elementarypriority.go
index d5b3f4a..5212afa 100644
--- a/queue/elementarypriority.go
+++ b/queue/elementarypriority.go
@@ -1,7 +1,7 @@
package queue
import (
- "algorithms/ds"
+ "github.com/snonux/algorithms/ds"
)
type ElementaryPriority struct {
diff --git a/queue/heappriority.go b/queue/heappriority.go
index d96975c..f88b9b3 100644
--- a/queue/heappriority.go
+++ b/queue/heappriority.go
@@ -1,7 +1,7 @@
package queue
import (
- "algorithms/ds"
+ "github.com/snonux/algorithms/ds"
)
type HeapPriority struct {
@@ -9,11 +9,11 @@ type HeapPriority struct {
}
func NewHeapPriority(capacity int) *HeapPriority {
- q := HeapPriority{
+ q := HeapPriority{
ElementaryPriority: ElementaryPriority{make(ds.ArrayList, 0, capacity), capacity},
}
- // Index 0 unused
+ // Index 0 unused
q.a = append(q.a, 0)
return &q
}
@@ -23,12 +23,12 @@ func (q *HeapPriority) Empty() bool {
}
func (q *HeapPriority) Size() int {
- return len(q.a)-1
+ return len(q.a) - 1
}
func (q *HeapPriority) Insert(a int) {
q.a = append(q.a, a)
- q.swim(len(q.a)-1)
+ q.swim(len(q.a) - 1)
}
func (q *HeapPriority) Max() (max int) {
@@ -50,7 +50,7 @@ func (q *HeapPriority) DeleteMax() int {
default:
a := q.a[1]
// Last index
- max := len(q.a)-1
+ max := len(q.a) - 1
q.a.Swap(1, max)
q.a = q.a[0:max]
@@ -63,13 +63,13 @@ func (q *HeapPriority) DeleteMax() int {
func (q *HeapPriority) swim(k int) {
for k > 1 && q.a[k/2] < q.a[k] {
q.a.Swap(k/2, k)
- k = k/2
+ k = k / 2
}
}
func (q *HeapPriority) sink(k int) {
// Last index
- max := len(q.a)-1
+ max := len(q.a) - 1
for 2*k <= max {
// Left child
@@ -77,7 +77,7 @@ func (q *HeapPriority) sink(k int) {
// Go to right child?
if j < max && q.a[j] < q.a[j+1] {
- j++
+ j++
}
// Found my spot in the heap
diff --git a/queue/queue_test.go b/queue/queue_test.go
index 2b32210..31ad020 100644
--- a/queue/queue_test.go
+++ b/queue/queue_test.go
@@ -1,9 +1,10 @@
package queue
import (
- "algorithms/ds"
"fmt"
"testing"
+
+ "github.com/snonux/algorithms/ds"
)
const minLength int = 1