README
¶
go-sliceheap
Package sliceheap returns a quick heap given a pointer to a slice and a less function (akin to sort.Slice for sorting slices).
This package is for that rare time when you need a heap and do not want to make
an arbitrary type to provide Push and Pop.
Documentation
Example
// we can create heap in one function and return it.
inner := func() sliceheap.Heap {
a := []int{3, 2, 4, 5, 1, 0, 6}
h := sliceheap.On(&a, func(i, j int) bool { return a[i] > a[j] })
heap.Init(h)
return h
}
h := inner()
// We can see the heap sort itself by checking the backing slice.
fmt.Println(h.View().([]int)) // prints [6 5 4 2 1 0 3]
// Push a few more elements.
heap.Push(h, 8)
// If we want to observe pushes and pops from the slice, we must save a
// pointer to the slice. This is only necessary if working on a slice
// that you did not pass directly to sliceheap.On, i.e., you have lost
// the original pointer you used.
ptr := h.Pointer().(*[]int)
fmt.Println(*ptr)
heap.Push(h, 7)
fmt.Println(*ptr)
heap.Push(h, 7)
heap.Push(h, 9)
// Pop everything off, printing as we pop largest to smallest.
for h.Len() > 0 {
largest := heap.Pop(h).(int)
fmt.Println(largest) // prints 9, 8, 7...
}
Benchmarks
The code works through heavy reflect usage. As such, it has many allocations. For normal one-off heaps, this should be a nonissue.
The following benchmark shows creating a slice of N nodes, and then constantly pushing a new largest element onto it and popping the smallest. The new largest element constantly sifts to the bottom, then smallest sifts out to be popped.
On go1.12.7,
BenchmarkPushPop/1_nodes-4 2000000 669 ns/op 124 B/op 6 allocs/op
BenchmarkPushPop/2_nodes-4 2000000 694 ns/op 128 B/op 6 allocs/op
BenchmarkPushPop/4_nodes-4 2000000 971 ns/op 138 B/op 8 allocs/op
BenchmarkPushPop/8_nodes-4 2000000 1102 ns/op 149 B/op 9 allocs/op
BenchmarkPushPop/16_nodes-4 1000000 1004 ns/op 145 B/op 9 allocs/op
BenchmarkPushPop/32_nodes-4 1000000 1161 ns/op 153 B/op 10 allocs/op
BenchmarkPushPop/64_nodes-4 1000000 1269 ns/op 160 B/op 11 allocs/op
BenchmarkPushPop/128_nodes-4 1000000 1453 ns/op 168 B/op 12 allocs/op
BenchmarkPushPop/256_nodes-4 1000000 1507 ns/op 176 B/op 13 allocs/op
BenchmarkPushPop/512_nodes-4 1000000 1667 ns/op 184 B/op 14 allocs/op
BenchmarkPushPop/1024_nodes-4 1000000 1781 ns/op 192 B/op 15 allocs/op
Documentation
¶
Overview ¶
Package sliceheap returns a quick heap interface implementation given a pointer to a slice and a less function (akin to sort.Slice for sorting slices).
This package is for that rare time when you need a heap and do not want to make an arbitrary type to provide Push and Pop.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap struct {
// contains filtered or unexported fields
}
Heap is a heap on a slice.
Example ¶
// inner shows that we can create heap in one function and return it.
inner := func() sliceheap.Heap {
a := []int{3, 2, 4, 5, 1, 0, 6}
h := sliceheap.On(&a, func(i, j int) bool { return a[i] > a[j] })
heap.Init(h)
return h
}
h := inner()
// We can see the heap sort itself by checking the backing slice.
fmt.Println(h.View().([]int))
// Push a few more elements.
heap.Push(h, 8)
// If we want to observe pushes and pops from the slice, we must save a
// pointer to the slice. This is only necessary if working on a slice
// that you did not pass directly to sliceheap.On, i.e., you have lost
// the original pointer you used.
ptr := h.Pointer().(*[]int)
fmt.Println(*ptr)
heap.Push(h, 7)
fmt.Println(*ptr)
heap.Push(h, 9)
// Pop everything off, printing as we pop largest to smallest.
for h.Len() > 0 {
largest := heap.Pop(h).(int)
fmt.Println(largest)
}
Output: [6 5 4 2 1 0 3] [8 6 4 5 1 0 3 2] [8 7 4 6 1 0 3 2 5] 9 8 7 6 5 4 3 2 1 0
func On ¶
On returns a heap on a pointer to a slice.
The heap is not initialized before returning.
Example ¶
a := []int{3, 2, 4, 5, 1, 0, 6}
h := sliceheap.On(&a, func(i, j int) bool { return a[i] > a[j] })
heap.Init(h)
fmt.Println(heap.Pop(h).(int))
Output: 6
func (Heap) Peek ¶
func (h Heap) Peek() interface{}
Peek returns a pointer to the element at index 0 in the heap, corresponding to the current smallest value.
Example ¶
a := []int{3, 1, 2}
h := sliceheap.On(&a, func(i, j int) bool { return a[i] < a[j] })
*h.Peek().(*int) = 4 // modify the first element
fmt.Println(a)
heap.Fix(h, 0) // and then fix its position
fmt.Println(a)
Output: [4 1 2] [1 4 2]
func (Heap) Pointer ¶
func (h Heap) Pointer() interface{}
Pointer returns a pointer to the backing slice the heap is on.
Changes to the heap can be seen by dereferencing the pointer.
func (Heap) Pop ¶
func (h Heap) Pop() interface{}
Pop pops the smallest element off of the slice and returns it.
Source Files