data-structures: github.com/bgadrian/data-structures/priorityqueue Index | Examples | Files

package priorityqueue

import "github.com/bgadrian/data-structures/priorityqueue"

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.

Index

Examples

Package Files

hierarchical_heap.go hierarchical_queue.go priorityqueue.go

type HierarchicalHeap Uses

type HierarchicalHeap struct {
    sync.Mutex
    // contains filtered or unexported fields
}

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! .

func NewHierarchicalHeap Uses

func NewHierarchicalHeap(buckets, pMin, pMax int, autoMutexLock bool) (*HierarchicalHeap, error)

NewHierarchicalHeap Generates a new HQ. 0 priority = max

func (*HierarchicalHeap) Dequeue Uses

func (h *HierarchicalHeap) Dequeue() (v interface{}, err error)

Dequeue Remove and return the highest key (lowest priority) O(log n/k)

func (*HierarchicalHeap) Enqueue Uses

func (h *HierarchicalHeap) Enqueue(value interface{}, priority int) error

Enqueue add a new key/value pair in the queue. 0 priority = max. O(log n/k)

func (*HierarchicalHeap) Len Uses

func (h *HierarchicalHeap) Len() int

Len Return the count of all values from all priorities. O(1)

type HierarchicalQueue Uses

type HierarchicalQueue struct {
    sync.Mutex
    // contains filtered or unexported fields
}

HierarchicalQueue An O(1)/O(1)* priority queue implementation for small integers See the README for more info.

Code:

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)

Output:

first is b

func NewHierarchicalQueue Uses

func NewHierarchicalQueue(lowestPriority uint8, autoMutexLock bool) *HierarchicalQueue

NewHierarchicalQueue Generates a new HQ

func (*HierarchicalQueue) Dequeue Uses

func (l *HierarchicalQueue) Dequeue() (v interface{}, err error)

Dequeue Return the highest priority value (0-highest priority, n-lowest)

func (*HierarchicalQueue) Enqueue Uses

func (l *HierarchicalQueue) Enqueue(value interface{}, priority uint8) (err error)

Enqueue Add a new element with a priority (0-highest priority, n-lowest)

func (*HierarchicalQueue) Len Uses

func (l *HierarchicalQueue) Len() int

Len Return the count of all values from all priorities

func (*HierarchicalQueue) LenPriority Uses

func (l *HierarchicalQueue) LenPriority(priority uint8) int

LenPriority Returns the count of all values from a specific priority queue

Package priorityqueue imports 4 packages (graph). Updated 2017-10-03. Refresh now. Tools for package owners.