README
¶
prioq
A priority queue package using a binary heap data structure in Go.
Built with Go 1.18 Generics support.
Adapted from heap
The API is still at an experimental phase.
Requirements
Go 1.18
If you've already have Go >=1.16i installed, you can get the beta with:
$ make go1.18
Example
values := []int{40, 30, 50, 100, 15}
pq := prioq.New[int](values)
var sorted []int
for !pq.IsEmpty() {
v, err := pq.Extract()
if err != nil {
log.Fatal(err)
}
sorted = append(sorted, v)
}
fmt.Println(sorted)
// Output:
// [15 30 40 50 100]
Documentation
¶
Overview ¶
Example (Items) ¶
This example shows how to implement your own CompareFunc and then use it on a defined type
package main
import (
"fmt"
"log"
"github.com/fsmiamoto/prioq"
)
// Item is an example defined type
type Item struct {
key int
}
// MaxItem is an example CompareFunc that builds a MaxHeap using the key property
func MaxItem(node, child Item) bool {
return child.key > node.key
}
// This example shows how to implement your own CompareFunc and then use it on
// a defined type
func main() {
values := []Item{
Item{key: 8},
Item{key: 22},
Item{key: 3},
Item{key: 14},
Item{key: 42},
}
pq := prioq.NewWithCompareFunc[Item](values, MaxItem)
for !pq.IsEmpty() {
item, err := pq.Extract()
if err != nil {
log.Fatal(err)
}
fmt.Println(item.key)
}
}
Output: 42 22 14 8 3
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CompareFunc ¶
CompareFunc is a generic function that compares two values and that should return true whenever those values should be swapped
type PrioQ ¶
type PrioQ[T any] struct { // contains filtered or unexported fields }
PrioQ represents a generic priority queue data structure
func New ¶
func New[T constraints.Ordered](elements []T) *PrioQ[T]
New creates a new priority queue for elements in the Ordered constraint.
func NewWithCompareFunc ¶
func NewWithCompareFunc[T any](elements []T, cf CompareFunc[T]) *PrioQ[T]
NewWithCompareFunc creates a new priority queue with the given initial capacity. Specifiing an initial capacity can be useful to avoid reallocations but in general you can just specify len(elements).
func (*PrioQ[T]) Extract ¶
Extract returns the element at the front of the queue It returns an errors whenever the queue is empty The time complexity is O(log(n)), n = # of elements in the queue
func (*PrioQ[T]) Insert ¶
func (h *PrioQ[T]) Insert(x T)
Insert adds a new element to the priority queue The time complexity is O(log(n)), n = # of elements in the priority queue
Source Files