Documentation
¶
Overview ¶
Package priorityqueue implements a priority queue (binary heap).
In computer science, a priority queue is an abstract data type similar to a regular queue or stack abstract data type. In a priority queue, each element has an associated priority, which determines its order of service. Priority queue serves highest priority items first. Priority values have to be instances of an ordered data type, and higher priority can be given either to the lesser or to the greater values with respect to the given order relation. For example, in Java standard library, PriorityQueue's the least elements with respect to the order have the highest priority. This implementation detail is without much practical significance, since passing to the opposite order relation turns the least values into the greatest, and vice versa.
Reference: https://en.wikipedia.org/wiki/Priority_queue
Index ¶
- type Element
- type Queue
- func (q *Queue[T]) Clear()
- func (q *Queue[T]) Dequeue() (value T, ok bool)
- func (q *Queue[T]) Elements() []*Element[T]
- func (q *Queue[T]) Enqueue(v T) *Element[T]
- func (q *Queue[T]) Fix(i int)
- func (q *Queue[T]) Len() int
- func (q *Queue[T]) MarshalJSON() ([]byte, error)
- func (q *Queue[T]) Peek() (value T, ok bool)
- func (q *Queue[T]) Remove(i int) (value T, ok bool)
- func (q *Queue[T]) String() string
- func (q *Queue[T]) UnmarshalJSON(data []byte) error
- func (q *Queue[T]) Update(i int, v T)
- func (q *Queue[T]) Values() []T
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Element ¶
type Element[T any] struct { Value T // the value stored with this element // contains filtered or unexported fields }
Element is an element of a priority queue.
type Queue ¶
type Queue[T any] struct { // contains filtered or unexported fields }
Queue represents an priority queue which holds the elements in a slice.
func New ¶
New returns an initialized priority queue with cmp.Less as the less function and the given values v added.
func NewFunc ¶
NewFunc returns an initialized priority queue with the given function less as the less function and the given values v added.
func (*Queue[T]) Dequeue ¶
Dequeue removes the first element if exists in queue and returns it. The ok result indicates whether such element was removed from queue.
func (*Queue[T]) Enqueue ¶
Enqueue adds the value v to the end of queue.
Example ¶
package main
import (
"fmt"
"github.com/docodex/gopkg/container/queue/priorityqueue"
)
func main() {
h := priorityqueue.NewFunc(func(a, b int) bool {
return a > b
})
h.Enqueue(3)
h.Enqueue(5)
h.Enqueue(1)
h.Enqueue(2)
v, _ := h.Peek()
fmt.Printf("maximum: %d\n", v)
for h.Len() > 0 {
v, _ := h.Dequeue()
fmt.Printf("%d ", v)
}
}
Output: maximum: 5 5 3 2 1
func (*Queue[T]) Fix ¶
Fix re-establishes queue ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling Queue.Remove followed by a Queue.Enqueue of the new value. The complexity is O(log n) where n = h.Len().
func (*Queue[T]) MarshalJSON ¶
MarshalJSON marshals queue into valid JSON. Ref: std json.Marshaler.
func (*Queue[T]) Peek ¶
Peek returns the first element if exists in queue without removing it. The ok result indicates whether such element was found in queue.
func (*Queue[T]) Remove ¶
Remove removes and returns the element at index i from queue. The complexity is O(log n) where n = h.Len().
func (*Queue[T]) UnmarshalJSON ¶
UnmarshalJSON unmarshals a JSON description of queue. The input can be assumed to be a valid encoding of a JSON value. UnmarshalJSON must copy the JSON data if it wishes to retain the data after returning. Ref: std json.Unmarshaler.
func (*Queue[T]) Update ¶
Update updates the element value to v at index i, and re-establishes heap ordering. Queue.Update is equivalent to, but less expensive than, calling Queue.Remove followed by a Queue.Enqueue of the new value. The complexity is O(log n) where n = h.Len().
Example ¶
package main
import (
"fmt"
"github.com/docodex/gopkg/container/queue/priorityqueue"
)
func main() {
// Some items and their priorities.
items := map[string]int{
"apple": 2, "pear": 4,
}
// An Item is something we manage in a priority queue.
type Item struct {
value string // The value of the item; arbitrary.
priority int // The priority of the item in queue.
}
// Create a priority queue, put the items in it, and
// establish the priority queue (heap) invariants.
q := priorityqueue.NewFunc(func(a, b *Item) bool {
return a.priority > b.priority
})
for value, priority := range items {
q.Enqueue(&Item{
value: value,
priority: priority,
})
}
// Insert a new item and then modify its priority.
orange := q.Enqueue(&Item{
value: "orange",
priority: 1,
})
orange.Value.priority = 5
q.Fix(orange.Index())
// Insert a new item and then update its priority.
banana := q.Enqueue(&Item{
value: "banana",
priority: 3,
})
q.Update(banana.Index(), &Item{
value: "banana",
priority: 1,
})
// Take the items out; they arrive in decreasing priority order.
for q.Len() > 0 {
item, _ := q.Dequeue()
fmt.Printf("%.2d:%s ", item.priority, item.value)
}
}
Output: 05:orange 04:pear 02:apple 01:banana
func (*Queue[T]) Values ¶
func (q *Queue[T]) Values() []T
Values returns all values in queue (in Queue.Dequeue order).
Source Files