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 ¶
- type Heap
- type MaxHeap
- func (p *MaxHeap) Insert(v interface{}, priority float64)
- func (p *MaxHeap) Len() int
- func (p *MaxHeap) Peek() (value interface{}, priority float64, err error)
- func (p *MaxHeap) Pop() (value interface{}, priority float64, err error)
- func (p *MaxHeap) UpdatePriority(x interface{}, newPriority float64)
- type MinHeap
- func (p *MinHeap) Insert(v interface{}, priority float64)
- func (p *MinHeap) Len() int
- func (p *MinHeap) Peek() (value interface{}, priority float64, err error)
- func (p *MinHeap) Pop() (value interface{}, priority float64, err error)
- func (p *MinHeap) UpdatePriority(x interface{}, newPriority float64)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type MaxHeap ¶
type MaxHeap struct {
// contains filtered or unexported fields
}
func NewMaxHeap ¶
func NewMaxHeap() MaxHeap
func (*MaxHeap) Insert ¶
Insert inserts a new element into the queue. No action is performed on duplicate elements.
func (*MaxHeap) Peek ¶
Peek returns the element with the highest priority from the queue. In case of an empty queue, an error is ret
func (*MaxHeap) Pop ¶
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 (*MaxHeap) UpdatePriority ¶
UpdatePriority changes the priority of a given item. If the specified item is not present in the queue, no action is performed.
type MinHeap ¶ added in v0.0.3
type MinHeap struct {
// contains filtered or unexported fields
}
MinHeap represents the queue
func NewMinHeap ¶ added in v0.0.3
func NewMinHeap() MinHeap
NewMinHeap initializes an empty priority queue.
func (*MinHeap) Insert ¶ added in v0.0.3
Insert inserts a new element into the queue. No action is performed on duplicate elements.
func (*MinHeap) Peek ¶ added in v0.0.3
Peek returns the element with the highest priority from the queue. In case of an empty queue, an error is ret
func (*MinHeap) Pop ¶ added in v0.0.3
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 (*MinHeap) UpdatePriority ¶ added in v0.0.3
UpdatePriority changes the priority of a given item. If the specified item is not present in the queue, no action is performed.