pq

README

An implementation of priority queue,ported from the beanstalkd

Features

• Push/Pop item
• Remove item on anywhere

Installing

To start using pq, install Go and run go get:

$ go get -u https://github.com/x-debug/pq

This will retrieve the library.

Example

You have to define the item structure first

type MinIntItem struct {
    value int
}

func (item MinIntItem) Less(other Item) bool {
    return item.value > other.(MinIntItem).value
}

Push item to PQ

pq := NewPriorityQueue()

pq.Push(MinIntItem{value: 3})
pq.Push(MinIntItem{value: 9})
pq.Push(MinIntItem{value: 1})

Pop item from PQ

item := pq.Pop().(MinIntItem)

Or remove item from PQ

item := pq.Remove(2).(MinIntItem)

more examples see pq_test.go

References

CMUQ 15-121 Priority Queues and Heaps

License

pq source code is available under the MIT License.

Documentation

Index

• type Item
• type PriorityQueue
  • func NewPriorityQueue() *PriorityQueue
  • func (pq *PriorityQueue) Len() int
  • func (pq *PriorityQueue) Pop() Item
  • func (pq *PriorityQueue) Push(ele Item)
  • func (pq *PriorityQueue) Remove(k int) Item

Types

type Item

type Item interface {
	Less(item Item) bool
}

Item is all elements must implement an interface

type PriorityQueue

type PriorityQueue struct {
	// contains filtered or unexported fields
}

PriorityQueue is an implementation of the priority queue, it can build a min/max order queue

func NewPriorityQueue

func NewPriorityQueue() *PriorityQueue

NewPriorityQueue construct a new priority queue

func (*PriorityQueue) Len

func (pq *PriorityQueue) Len() int

Len return length of PQ

func (*PriorityQueue) Pop

func (pq *PriorityQueue) Pop() Item

Pop removes an element, return an element to the caller, it adjusts orders of all items automatically

func (*PriorityQueue) Push

func (pq *PriorityQueue) Push(ele Item)

Push an element to PQ, it adjusts orders of all items automatically

func (*PriorityQueue) Remove

func (pq *PriorityQueue) Remove(k int) Item

Remove also see Pop method, but it can select anywhere