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 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) |
| 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 | 47.72 ns/op/node | 107.4 ns/node | 523.2 ns/op/node |
| Pairing | 41.91 ns/op/node | 69.96 ns/node | 792.2 ns/op/node |
| Skew | 184.3 ns/op/node | 381.5 ns/node | 562.1 ns/op/node |
| Skew Binomial | 59.72 ns/op/node | 121.4 ns/node | 1001 ns/op/node |
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 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