Package priorityqueue implements a series of performant, concurrency safe data structures used for priority queues.
Hierarchical Queue - O(1) priority queues for large amounts of small priorities (uint8)
Hierarchical Heap - O(log n/k) priority queue for large amounts of data, slower than HQ but has no limitations.
HierarchicalHeap It is a modification of the Hierarchical Queue structure, adding some complexity (O(log n/k)) but removing it's limitations. Inspired by [Cris L. Luengo Hendriks paper](http://www.cb.uu.se/~cris/Documents/Luengo2010a_preprint.pdf)
Unlike HQ that has 1 bucket for each priority value, HHeap priorities are grouped (using a linear mapping formula) in K buckets. Buckets are Implicit heaps (special binary tree) that stores all values for a specific range of priorities. Example: pMin=0, pMax=100 (0-100 priorities), K=15 (buckets) Enqueue("a", 21) will add "a" to bucket i, where i = (21 − pmin) / (pmax − pmin) * K = 3
For the best performance benchmark the Enq/Deq functions with your own data, and tweak the buckets,minP,maxP parameters! .
NewHierarchicalHeap Generates a new HQ. 0 priority = max
Dequeue Remove and return the highest key (lowest priority) O(log n/k)
Enqueue add a new key/value pair in the queue. 0 priority = max. O(log n/k)
Len Return the count of all values from all priorities. O(1)
HierarchicalQueue An O(1)/O(1)* priority queue implementation for small integers See the README for more info.
autoLockMutex := false var lowestPriority uint8 = 10 //highest is 0 l := NewHierarchicalQueue(lowestPriority, autoLockMutex) l.Enqueue("a", 2) l.Enqueue("b", 0) first, _ := l.Dequeue() fmt.Printf("first is %v", first)
first is b
NewHierarchicalQueue Generates a new HQ
Dequeue Return the highest priority value (0-highest priority, n-lowest)
Enqueue Add a new element with a priority (0-highest priority, n-lowest)
Len Return the count of all values from all priorities
LenPriority Returns the count of all values from a specific priority queue