README
¶
priorityqueue
A fast, generic, thread safe priority queue for Go 1.18+.
Features
- Minimal API
- Generic initializers – anything that can be ordered can be put into the queue
- Built-in thread safety
- Speed – see benchmarks
TODO
- Documentation
- Benchmarks
- Concurrency tests
Under the hood
The priority queue implements a binary heap (using container/heap from the standard library).
Benchmarks
A priority queue is populated to a given size, we then measure the performance of Push/Pop/Peek.
Two benchmarks for Push are measured: PushMin pushes the lowest priority item into the queue, which represents the best-case swim-up scenario. Conversely, PushMax pushes the highest priority item into the queue, which represents the worst-case swim-up scenario.
goos: windows
goarch: amd64
pkg: github.com/jamesrom/priorityqueue
cpu: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz
BenchmarkPushMaxOntoSize10-8 8987006 142.5 ns/op 51 B/op 0 allocs/op
BenchmarkPushMaxOntoSize100-8 9489698 135.7 ns/op 49 B/op 0 allocs/op
BenchmarkPushMaxOntoSize1000-8 9486435 137.9 ns/op 49 B/op 1 allocs/op
BenchmarkPushMaxOntoSize10000-8 9446527 136.0 ns/op 49 B/op 1 allocs/op
BenchmarkPushMaxOntoSize100000-8 9374347 136.4 ns/op 49 B/op 1 allocs/op
BenchmarkPushMaxOntoSize1000000-8 9056944 142.9 ns/op 57 B/op 1 allocs/op
BenchmarkPushMaxOntoSize10000000-8 8540882 150.5 ns/op 40 B/op 1 allocs/op
BenchmarkPushMinOntoSize10-8 25805064 45.41 ns/op 54 B/op 1 allocs/op
BenchmarkPushMinOntoSize100-8 26073862 45.74 ns/op 54 B/op 1 allocs/op
BenchmarkPushMinOntoSize1000-8 26361690 44.61 ns/op 53 B/op 1 allocs/op
BenchmarkPushMinOntoSize10000-8 26388182 41.99 ns/op 53 B/op 1 allocs/op
BenchmarkPushMinOntoSize100000-8 26091663 42.56 ns/op 53 B/op 1 allocs/op
BenchmarkPushMinOntoSize1000000-8 27603910 41.52 ns/op 50 B/op 1 allocs/op
BenchmarkPushMinOntoSize10000000-8 32006144 46.13 ns/op 51 B/op 1 allocs/op
BenchmarkPopFromSize10-8 6760711 202.0 ns/op 7 B/op 0 allocs/op
BenchmarkPopFromSize100-8 6468810 206.4 ns/op 7 B/op 0 allocs/op
BenchmarkPopFromSize1000-8 6283765 204.2 ns/op 8 B/op 1 allocs/op
BenchmarkPopFromSize10000-8 6299400 218.0 ns/op 8 B/op 1 allocs/op
BenchmarkPopFromSize100000-8 6451550 215.1 ns/op 8 B/op 1 allocs/op
BenchmarkPopFromSize1000000-8 5741742 216.7 ns/op 8 B/op 1 allocs/op
BenchmarkPopFromSize10000000-8 5393007 223.3 ns/op 8 B/op 1 allocs/op
BenchmarkPeekFromSize10-8 92274331 12.88 ns/op 0 B/op 0 allocs/op
BenchmarkPeekFromSize100-8 92274331 12.94 ns/op 0 B/op 0 allocs/op
BenchmarkPeekFromSize1000-8 92299881 13.04 ns/op 0 B/op 0 allocs/op
BenchmarkPeekFromSize10000-8 92272202 12.86 ns/op 0 B/op 0 allocs/op
BenchmarkPeekFromSize100000-8 92318343 12.87 ns/op 0 B/op 0 allocs/op
BenchmarkPeekFromSize1000000-8 92499093 12.88 ns/op 0 B/op 0 allocs/op
BenchmarkPeekFromSize10000000-8 96001536 12.92 ns/op 0 B/op 0 allocs/op
PASS
coverage: 69.0% of statements
ok github.com/jamesrom/priorityqueue 75.666s
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Prioritizable ¶
type Prioritizable interface {
Priority() int
}
type PriorityQueue ¶
type PriorityQueue[T any] struct { // contains filtered or unexported fields }
func NewPriority ¶
func NewPriority[T Prioritizable](items ...T) *PriorityQueue[T]
NewPriority - highest priority / descending order / maxheap
func NewSimple ¶
func NewSimple[T compare.SimpleOrdered](items ...T) *PriorityQueue[T]
NewSimple - ascending order / minheap
func NewWithComparator ¶
func NewWithComparator[T any](fn compare.LessFunc[T], items ...T) *PriorityQueue[T]
NewWithComparator - order defined by a custom less function
func (*PriorityQueue[T]) Len ¶
func (p *PriorityQueue[T]) Len() int
Len returns the size of the queue
func (*PriorityQueue[T]) Peek ¶
func (p *PriorityQueue[T]) Peek() T
Peek keeps the top element in the queue and returns it's value
func (*PriorityQueue[T]) Pop ¶
func (p *PriorityQueue[T]) Pop() T
Pop returns the element at the head of the queue and removes it from the queue
func (*PriorityQueue[T]) Push ¶
func (p *PriorityQueue[T]) Push(x T)
Pushes x into the priority queue
Source Files