Documentation
¶
Overview ¶
Package pq implements a priority queue data structure on top of container/heap. As an addition to regular operations, it allows an update of an items priority, allowing the queue to be used in graph search algorithms like Dijkstra's algorithm. Computational complexities of operations are mainly determined by container/heap. In addition, a map of items is maintained, allowing O(1) lookup needed for priority updates, which themselves are O(log n).
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
PriorityQueue represents the queue
func NewWithMaxSize ¶ added in v1.0.1
func NewWithMaxSize(maxSize int) PriorityQueue
func (*PriorityQueue) Insert ¶
func (p *PriorityQueue) Insert(v Queuable, priority, secondaryPrio float64)
Insert inserts a new element into the queue. No action is performed on duplicate elements.
func (*PriorityQueue) Len ¶
func (p *PriorityQueue) Len() int
Len returns the number of elements in the queue.
func (*PriorityQueue) Pop ¶
func (p *PriorityQueue) Pop() (Queuable, error)
Pop removes the element with the highest priority from the queue and returns it. In case of an empty queue, an error is returned.
func (*PriorityQueue) UpdatePriority ¶
func (p *PriorityQueue) UpdatePriority(x Queuable, newPriority float64)
UpdatePriority changes the priority of a given item. If the specified item is not present in the queue, no action is performed.
Source Files