README
¶
Package cloudeng.io/algo/container/heap
import cloudeng.io/algo/container/heap
Functions
Func Fix
func Fix[T Value[T]](h []T, i int)
Fix is like heap.Fix.
Types
Type Heap
type Heap[T Value[T]] []T
Heap is a generic heap implementation that can be used with any type that implements the Value interface. It provides methods to push, pop, remove, and fix elements in the heap. The heap is implemented as a slice in the same manner as the standard library's heap package, but it is generic and can work with any type that satisfies the Value interface.
Methods
func (h Heap[T]) Init()
func (h Heap[T]) Len() int
func (h *Heap[T]) Pop() T
Pop is like heap.Pop.
func (h *Heap[T]) Push(x T)
Push is like heap.Push.
func (h *Heap[T]) Remove(i int) T
Remove is like heap.Remove.
Type MinMax
type MinMax[K Ordered, V any] struct {
Keys []K
Vals []V
// contains filtered or unexported fields
}
MinMax represents a min-max heap as described in: https://liacs.leidenuniv.nl/~stefanovtp/courses/StudentenSeminarium/Papers/AL/SMMH.pdf. Note that this requires the use of a dummy root node in the key and value slices, ie. Keys[0] and Values[0] is always empty.
Functions
func NewMinMax[K Ordered, V any](opts ...Option[K, V]) *MinMax[K, V]
NewMinMax creates a new instance of MinMax.
Methods
func (h *MinMax[K, V]) Len() int
Len returns the number of items stored in the heap, excluding the dummy root node.
func (h *MinMax[K, V]) PopMax() (K, V)
PopMax removes and returns the largest key/value pair from the heap.
func (h *MinMax[K, V]) PopMin() (K, V)
PopMin removes and returns the smallest key/value pair from the heap.
func (h *MinMax[K, V]) Push(k K, v V)
Push pushes the key/value pair onto the heap.
func (h *MinMax[K, V]) PushMaxN(k K, v V, n int)
PushMaxN pushes the key/value pair onto the heap if the key is greater than than the current maximum whilst ensuring that the heap is no larger than n.
func (h *MinMax[K, V]) PushMinN(k K, v V, n int)
PushMinN pushes the key/value pair onto the heap if the key is less than the current minimum whilst ensuring that the heap is no larger than n.
func (h *MinMax[K, V]) Remove(i int) (k K, v V)
Remove removes the i'th item from the heap, note that i includes the dummy root, i.e. i == 0 is the dummy root, 1 is the min, 2 is the max etc. Deleting the dummy root has no effect.
func (h *MinMax[K, V]) Update(i int, k K, v V)
Update updates the i'th item in the heap, note that i includes the dummy root element. This is more efficient than removing and adding an item.
Type Option
type Option[K Ordered, V any] func(*options[K, V])
Option represents the options that can be passed to NewMin and NewMax.
Functions
func WithCallback[K Ordered, V any](fn func(iv, jv V, i, j int)) Option[K, V]
WithCallback provides a callback function that is called after every operation with the values and indices of the elements that have changed location. Note that is not sufficient to track removal of items and hence any applications that requires such tracking should do so explicitly by wrapping the Pop operations and deleting the retried item from their data structures.
func WithData[K Ordered, V any](keys []K, vals []V) Option[K, V]
WithData sets the initial data for the heap.
func WithSliceCap[K Ordered, V any](n int) Option[K, V]
WithSliceCap sets the initial capacity of the slices used to hold keys and values.
Type Ordered
type Ordered interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 |
~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | string
}
Orderded represents the set of types that can be used as keys in a heap.
Type T
type T[K Ordered, V any] struct {
Keys []K
Vals []V
// contains filtered or unexported fields
}
T represents a heap of keys and values.
Functions
func NewMax[K Ordered, V any](opts ...Option[K, V]) *T[K, V]
NewMax creates a new heap with descending order.
func NewMin[K Ordered, V any](opts ...Option[K, V]) *T[K, V]
NewMin creates a new heap with ascending order.
Methods
func (h *T[K, V]) Len() int
Len returns the number of elements in the heap.
func (h *T[K, V]) Pop() (K, V)
Pop removes and returns the top element from the heap.
func (h *T[K, V]) Push(k K, v V)
Push adds a new key and value to the heap.
func (h *T[K, V]) Remove(i int) (K, V)
Remove removes the i'th element from the heap.
func (h *T[K, V]) Update(pos int, k K, v V)
Update updates the key and value for the i'th element in the heap. It is more efficient than Remove followed by Push.
Type Value
type Value[T any] interface {
Less(x T) bool
}
Value represents the interface that must be implemented by types that can be used as values in the generic Heap implementation. It requires a Less method that compares the current instance with another instance of the same type and returns true if the current instance is less than the other instance.
Examples
ExampleHeap
Documentation
¶
Index ¶
- func Fix[T Value[T]](h []T, i int)
- type Heap
- type MinMax
- func (h *MinMax[K, V]) Len() int
- func (h *MinMax[K, V]) PopMax() (K, V)
- func (h *MinMax[K, V]) PopMin() (K, V)
- func (h *MinMax[K, V]) Push(k K, v V)
- func (h *MinMax[K, V]) PushMaxN(k K, v V, n int)
- func (h *MinMax[K, V]) PushMinN(k K, v V, n int)
- func (h *MinMax[K, V]) Remove(i int) (k K, v V)
- func (h *MinMax[K, V]) Update(i int, k K, v V)
- type Option
- type Ordered
- type T
- type Value
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Heap ¶
type Heap[T Value[T]] []T
Heap is a generic heap implementation that can be used with any type that implements the Value interface. It provides methods to push, pop, remove, and fix elements in the heap. The heap is implemented as a slice in the same manner as the standard library's heap package, but it is generic and can work with any type that satisfies the Value interface.
Example ¶
package main
import (
"fmt"
"cloudeng.io/algo/container/heap"
)
type Example struct {
idx int
val string
}
func (e Example) Less(b Example) bool {
return e.idx < b.idx
}
func main() {
h := heap.Heap[Example]{
{idx: 3, val: "three"},
{idx: 1, val: "one"},
{idx: 2, val: "two"},
{idx: 0, val: "zero"},
}
h.Init()
for h.Len() > 0 {
v := h.Pop()
fmt.Printf("%v %v ", v.idx, v.val)
}
fmt.Println()
}
Output: 0 zero 1 one 2 two 3 three
type MinMax ¶
type MinMax[K Ordered, V any] struct { Keys []K Vals []V // contains filtered or unexported fields }
MinMax represents a min-max heap as described in: https://liacs.leidenuniv.nl/~stefanovtp/courses/StudentenSeminarium/Papers/AL/SMMH.pdf. Note that this requires the use of a dummy root node in the key and value slices, ie. Keys[0] and Values[0] is always empty.
func NewMinMax ¶
NewMinMax creates a new instance of MinMax.
Example ¶
package main
import (
"fmt"
"strconv"
"cloudeng.io/algo/container/heap"
)
func main() {
h := heap.NewMinMax[int, string]()
for _, i := range []int{12, 32, 25, 36, 13, 23, 26, 42, 49, 7, 15, 63, 92, 5} {
h.Push(i, strconv.Itoa(i))
}
for h.Len() > 0 {
k, _ := h.PopMin()
fmt.Printf("%v ", k)
k, _ = h.PopMax()
fmt.Printf("%v ", k)
}
fmt.Println()
}
Output: 5 92 7 63 12 49 13 42 15 36 23 32 25 26
func (*MinMax[K, V]) Len ¶
Len returns the number of items stored in the heap, excluding the dummy root node.
func (*MinMax[K, V]) PopMax ¶
func (h *MinMax[K, V]) PopMax() (K, V)
PopMax removes and returns the largest key/value pair from the heap.
func (*MinMax[K, V]) PopMin ¶
func (h *MinMax[K, V]) PopMin() (K, V)
PopMin removes and returns the smallest key/value pair from the heap.
func (*MinMax[K, V]) Push ¶
func (h *MinMax[K, V]) Push(k K, v V)
Push pushes the key/value pair onto the heap.
func (*MinMax[K, V]) PushMaxN ¶
PushMaxN pushes the key/value pair onto the heap if the key is greater than than the current maximum whilst ensuring that the heap is no larger than n.
func (*MinMax[K, V]) PushMinN ¶
PushMinN pushes the key/value pair onto the heap if the key is less than the current minimum whilst ensuring that the heap is no larger than n.
type Option ¶
Option represents the options that can be passed to NewMin and NewMax.
func WithCallback ¶
WithCallback provides a callback function that is called after every operation with the values and indices of the elements that have changed location. Note that is not sufficient to track removal of items and hence any applications that requires such tracking should do so explicitly by wrapping the Pop operations and deleting the retried item from their data structures.
type Ordered ¶
type Ordered interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 |
~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | string
}
Orderded represents the set of types that can be used as keys in a heap.
type T ¶
T represents a heap of keys and values.
func NewMax ¶
NewMax creates a new heap with descending order.
Example ¶
package main
import (
"fmt"
"strconv"
"cloudeng.io/algo/container/heap"
)
func main() {
h := heap.NewMax[int, string]()
for _, i := range []int{100, 19, 36, 17, 3, 25, 1, 2, 7} {
h.Push(i, strconv.Itoa(i))
}
for h.Len() > 0 {
k, _ := h.Pop()
fmt.Printf("%v ", k)
}
fmt.Println()
}
Output: 100 36 25 19 17 7 3 2 1
func NewMin ¶
NewMin creates a new heap with ascending order.
Example ¶
package main
import (
"fmt"
"strconv"
"cloudeng.io/algo/container/heap"
)
func main() {
h := heap.NewMin[int, string]()
for _, i := range []int{100, 19, 36, 17, 3, 25, 1, 2, 7} {
h.Push(i, strconv.Itoa(i))
}
for h.Len() > 0 {
k, _ := h.Pop()
fmt.Printf("%v ", k)
}
fmt.Println()
}
Output: 1 2 3 7 17 19 25 36 100
func (*T[K, V]) Pop ¶
func (h *T[K, V]) Pop() (K, V)
Pop removes and returns the top element from the heap.
type Value ¶
Value represents the interface that must be implemented by types that can be used as values in the generic Heap implementation. It requires a Less method that compares the current instance with another instance of the same type and returns true if the current instance is less than the other instance.
Source Files