README
¶
Package cloudeng.io/algo/container/heap
import cloudeng.io/algo/container/heap
Types
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.
Documentation
¶
Index ¶
- 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
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
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.
Source Files