README
¶
Heap structure, using go generics
Introduction
The Heap package contains simple binary heap implementation, using Golang generics. There are several heap implementations
- generic Heap implementation, that could be used for
anytype, ComparableHeapfor comparable types. AdditionalSearchandDeleteare implemented,- for
constraints.Orderedthere are constructors for min, max heaps;
Also use-cases provided:
TopNthat allows getting N top elements from slice.TopNswaps top N elements to first N elements of slice, no additional allocations are done. All slice elements are kept, only order is changed.TopNHeapallows to get N top, pushing elements from stream without allocation slice for all elements. Only O(N) memory is used.TopNImmutableallocated new slice for heap, input slice is not mutated.
Both TopN and TopNImmutable has methods for creating min and max tops for constraints.Ordered.
Usage Example
package main
import (
"fmt"
"github.com/lispad/go-generics-tools/binheap"
)
func main() {
someData := []float64{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
mins := binheap.MinN[float64](someData, 3)
fmt.Printf("--- top 3 min elements: %v\n", mins)
maxs := binheap.MaxN[float64](someData, 3)
fmt.Printf("--- top 3 max elements: %v\n\n", maxs)
heap := binheap.EmptyMaxHeap[string]()
heap.Push("foo")
heap.Push("zzz")
heap.Push("bar")
heap.Push("baz")
heap.Push("foobar")
heap.Push("foobaz")
fmt.Printf("--- heap has %d elements, max element:\n%s\n\n", heap.Len(), heap.Peak())
}
A bit more examples could be found in examples directory
Benchmark
Theoretical complexity for getting TopN from slice with size M, N <= M: O(N*ln(M)). When N << M, the heap-based TopN could be much faster than sorting slice and getting top. E.g. For top-3 from 10k elements approach is ln(10^5)/ln(3) ~= 8.38 times faster.
Benchmark
BenchmarkSortedMaxN-8 10303648 136.0 ns/op 0 B/op 0 allocs/op
BenchmarkMaxNImmutable-8 398996316 3.029 ns/op 0 B/op 0 allocs/op
BenchmarkMaxN-8 804041455 1.819 ns/op 0 B/op 0 allocs/op
Compatibility
Minimal Golang version is 1.18. Generics and fuzz testing are used.
Installation
To install package, run:
go get github.com/lispad/go-generics-tools/binheap
License
The binheap package is licensed under the MIT license. Please see the LICENSE file for details.
Documentation
¶
Overview ¶
Package binheap provides implementation of binary heap for any type with use of golang generics, and top-N heap usecases.
Index ¶
- func MaxN[T constraints.Ordered](data []T, n int) []T
- func MaxNImmutable[T constraints.Ordered](data []T, n int) []T
- func MinN[T constraints.Ordered](data []T, n int) []T
- func MinNImmutable[T constraints.Ordered](data []T, n int) []T
- func TopN[T any](data []T, n int, comparator func(x, y T) bool) []T
- func TopNImmutable[T any](data []T, n int, comparator func(x, y T) bool) []T
- type ComparableHeap
- func ComparableFromSlice[T comparable](data []T, comparator func(x, y T) bool) ComparableHeap[T]
- func EmptyComparableHeap[T comparable](comparator func(x, y T) bool) ComparableHeap[T]
- func EmptyMaxHeap[T constraints.Ordered]() ComparableHeap[T]
- func EmptyMinHeap[T constraints.Ordered]() ComparableHeap[T]
- func MaxHeapFromSlice[T constraints.Ordered](data []T) ComparableHeap[T]
- func MinHeapFromSlice[T constraints.Ordered](data []T) ComparableHeap[T]
- type Heap
- type TopNHeap
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func MaxN ¶
func MaxN[T constraints.Ordered](data []T, n int) []T
MaxN moves N Max elements of slice to the beginning and returns subslice of first n elements. Mutates source data slice. No additional allocations are done.
func MaxNImmutable ¶
func MaxNImmutable[T constraints.Ordered](data []T, n int) []T
MaxNImmutable return n maximal elements from slice. O(M *ln(N)), where M is slice size Allocates new slice, source data isn't mutated. O(N) additional allocations.
func MinN ¶
func MinN[T constraints.Ordered](data []T, n int) []T
MinN moves N Min elements of slice to the beginning and returns subslice of first n elements. Mutates source data slice. No additional allocations are done.
func MinNImmutable ¶
func MinNImmutable[T constraints.Ordered](data []T, n int) []T
MinNImmutable return n minimal elements from slice. O(M *ln(N)), where M is slice size Allocates new slice, source data isn't mutated. O(N) additional allocations.
func TopN ¶
TopN mutates data slice, moving TopN elements of slice to the beginning and returns subslice of first n elements. O(M *ln(N)), where M is slice size Mutates source data slice. No additional allocations are done.
func TopNImmutable ¶
TopNImmutable returns top n elements from slice. O(M *ln(N)), where M is slice size Allocates new slice, source data isn't mutated. O(N) additional allocations.
Types ¶
type ComparableHeap ¶
type ComparableHeap[T comparable] struct { Heap[T] }
ComparableHeap provides additional Search and Delete methods. Could be used for comparable types.
func ComparableFromSlice ¶
func ComparableFromSlice[T comparable](data []T, comparator func(x, y T) bool) ComparableHeap[T]
ComparableFromSlice creates heap, based on provided slice. Slice could be reordered.
func EmptyComparableHeap ¶
func EmptyComparableHeap[T comparable](comparator func(x, y T) bool) ComparableHeap[T]
EmptyComparableHeap creates heap for comparable types.
func EmptyMaxHeap ¶
func EmptyMaxHeap[T constraints.Ordered]() ComparableHeap[T]
EmptyMaxHeap creates empty Max-Heap for ordered types.
func EmptyMinHeap ¶
func EmptyMinHeap[T constraints.Ordered]() ComparableHeap[T]
EmptyMinHeap creates empty Min-Heap for ordered types.
func MaxHeapFromSlice ¶
func MaxHeapFromSlice[T constraints.Ordered](data []T) ComparableHeap[T]
EmptyMaxHeap creates Max-Heap, based on provided slice. Slice could be reordered.
func MinHeapFromSlice ¶
func MinHeapFromSlice[T constraints.Ordered](data []T) ComparableHeap[T]
EmptyMinHeap creates Min-Heap, based on provided slice. Slice could be reordered.
func (*ComparableHeap[T]) Delete ¶
func (h *ComparableHeap[T]) Delete(x T) bool
Delete removes element from heap, and returns true if x presents in heap.
func (*ComparableHeap[T]) Search ¶
func (h *ComparableHeap[T]) Search(x T) bool
Search returns if element presents in heap.
type Heap ¶
type Heap[T any] struct { // contains filtered or unexported fields }
Heap provides basic methods: Push, Peak, Pop, Replace top element and PushPop.
type TopNHeap ¶
type TopNHeap[T any] struct { // contains filtered or unexported fields }
TopNHeap keeps N top elements in reverse order.
func EmptyTopNHeap ¶
EmptyTopNHeap creates new heap for storing n top elements.
func (*TopNHeap[T]) PeekTopN ¶
func (h *TopNHeap[T]) PeekTopN() []T
PeekTopN returns current top N elements.
Source Files