README
¶
gopq
A simple and generic priority queue implementation in Golang.
API
Any such type that implements the Heapable interface may be used in a PriorityQueue.
The underlying element essentially must know how to give priority when compared to another
element of the same type.
If the priority queue does not require modifications (i.e. updates or removals), the type
implementing Heapable does not need to support indexing.
type myType struct {
priority int
}
func (th *testHeapable) Index() (i int) { return }
func (th *testHeapable) SetIndex(_ int) {}
func (mt *myType) Priority(other interface{}) bool {
if t, ok := other.(*myType); ok {
return th.priority > t.priority
}
return false
}
pq := NewPriorityQueue()
pq.Push(&myType{priority: 1})
pq.Push(&myType{priority: 3})
pq.Push(&myType{priority: 2})
for pq.Size() != 0 {
res, err := pq.Pop()
// ...
}
Tests
$ go test -v ./...
Contributing
- Fork it
- Create your feature branch (
git checkout -b feature/my-new-feature) - Commit your changes (
git commit -m 'Add some feature') - Push to the branch (
git push origin feature/my-new-feature) - Create a new Pull Request
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heapable ¶
Heapable reflects an interface that an item must implement in order to be placed into a priority queue. If the priority queue does not require modifications (i.e. updates or removals), these can be implemented as no-ops.
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
PriorityQueue implements a priority queue of Heapable items. Each item must implement the Heapable interface and is responsible for giving each item priority respective to every other item. The main benefit of this implementation is to abstract away any direct heap usage.
func NewPriorityQueue ¶
func NewPriorityQueue() *PriorityQueue
NewPriorityQueue returns a reference to a new initialized PriorityQueue.
func (*PriorityQueue) Pop ¶
func (pq *PriorityQueue) Pop() (res Heapable, err error)
Pop removes a Sortable item from the priority queue with the highest priority and returns it. The complexity is logarithmic. If the index is beyond the size of the priority queue, an error is returned.
func (*PriorityQueue) Push ¶
func (pq *PriorityQueue) Push(h Heapable)
Push adds a Sortable item to the priority queue. The complexity is logarithmic.
func (*PriorityQueue) Remove ¶
func (pq *PriorityQueue) Remove(h Heapable) (err error)
Remove removes a Heapable item from the priority queue. The item is retrieved by fetching it's index. Items are then "fixed" into their appropriate order once the item is removed. The complexity is logarithmic. If the index is beyond the size of the priority queue, an error is returned.
func (*PriorityQueue) Size ¶
func (pq *PriorityQueue) Size() int
Size returns the size of the priority queue.
func (*PriorityQueue) Update ¶
func (pq *PriorityQueue) Update(h Heapable) (err error)
Update re-establishes the priority queue ordering after the Heapable element has changed its value. It is up to the caller to update the element accordingly. The complexity is logarithmic. If the index is beyond the size of the priority queue, an error is returned.
Source Files