README
¶
pqueue
A collection of concurrency-safe generic priority queue implementations.
[!NOTE] This package is under development, and I plan to add more implementations in the future.
About
Every priority queue (except Circular FIFO, obviously) in this package is a generic struct, where key K has constraint
cmp.Ordered and value V has constraint any. All priority queues are min-heap-based (i.e., the smallest key has the
highest priority) and allow for duplicate keys/priorities.
Contributing
I am just one guy working on this in my free time for fun. So, if you have any suggestions or issues, please feel free to open an issue or pull request!
Implementations
Currently, this package provides the following queues.
Time Complexities
| Type | findMin | removeMin | insert | meld |
|---|---|---|---|---|
| Binary | Θ(1) | Θ(log n) | Θ(log n) | Θ(n) |
| Circular FIFO | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
| Pairing | Θ(1) | O(log n) am. | Θ(1) | Θ(1) |
| Skew | Θ(1) | O(log n) am. | O(log n) am. | O(log n) am. |
| Skew Binomial | Θ(1) | Θ(log n) | Θ(1) | Θ(log n) |
Benchmarks
Apple MacBook Pro (M4 Pro, 24GB RAM)
| Type | push | meld | pop |
|---|---|---|---|
| Binary | 49.40 ns/op | 17.72 ns/node | 502.7 ns/op |
| Circular FIFO | 24.46 ns/op | 2.58×10-5 ns/node | 5.945 ns/op |
| Pairing | 48.17 ns/op | 4.83×10-4 ns/node | 728.0 ns/op |
| Skew | 193.6 ns/op | 3.103×10-4 ns/node | 587.9 ns/op |
| Skew Binomial | 62.05 ns/op | 6.102×10-4 ns/node | 1070 ns/op |
Documentation
¶
Overview ¶
Package pqueue provides concurrency-safe priority queue implementations.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var (
ConcurrencySafetyError = errors.New("concurrency-safety error: one or more queues share the same underlying" +
"ID. ensure that all queues are being created via their designated constructors")
)
Functions ¶
This section is empty.
Types ¶
type Binary ¶ added in v1.1.0
Binary is a concurrency-safe, min-priority queue built on a binary heap.
type CircularBuffer ¶ added in v1.2.0
type CircularBuffer[T any] struct { // contains filtered or unexported fields }
func NewCircularBuffer ¶ added in v1.2.0
func NewCircularBuffer[T any]() *CircularBuffer[T]
func (*CircularBuffer[T]) Clear ¶ added in v1.2.2
func (cb *CircularBuffer[T]) Clear()
func (*CircularBuffer[T]) Meld ¶ added in v1.2.0
func (cb *CircularBuffer[T]) Meld(other *CircularBuffer[T])
func (*CircularBuffer[T]) Peek ¶ added in v1.2.0
func (cb *CircularBuffer[T]) Peek() T
func (*CircularBuffer[T]) Pop ¶ added in v1.2.0
func (cb *CircularBuffer[T]) Pop() (v T, ok bool)
func (*CircularBuffer[T]) Push ¶ added in v1.2.0
func (cb *CircularBuffer[T]) Push(v T)
func (*CircularBuffer[T]) Size ¶ added in v1.2.2
func (cb *CircularBuffer[T]) Size() int
type CrossMeldable ¶ added in v1.2.0
type CrossMeldable interface {
CrossMeld(other CrossMeldable)
}
type Pairing ¶
Pairing is a concurrency-safe, min-priority queue built on a pairing heap.
type Skew ¶
Skew is a concurrency-safe, min-priority queue built on a skew heap.
type SkewBinomial ¶ added in v1.1.0
SkewBinomial is a concurrency-safe, min-priority queue built on a skew binomial heap.
func NewSkewBinomial ¶ added in v1.1.0
func NewSkewBinomial[K cmp.Ordered, V any]() *SkewBinomial[K, V]
func (*SkewBinomial[K, V]) Clear ¶ added in v1.1.0
func (sb *SkewBinomial[K, V]) Clear()
func (*SkewBinomial[K, V]) Meld ¶ added in v1.1.0
func (sb *SkewBinomial[K, V]) Meld(other *SkewBinomial[K, V])
func (*SkewBinomial[K, V]) Peek ¶ added in v1.1.0
func (sb *SkewBinomial[K, V]) Peek() V
func (*SkewBinomial[K, V]) Pop ¶ added in v1.1.0
func (sb *SkewBinomial[K, V]) Pop() (v V, ok bool)
func (*SkewBinomial[K, V]) Push ¶ added in v1.1.0
func (sb *SkewBinomial[K, V]) Push(v V, priority K)
func (*SkewBinomial[K, V]) Size ¶ added in v1.1.0
func (sb *SkewBinomial[K, V]) Size() int
Source Files
Directories