heap

Documentation

Index

• type Heap
  • func NewHeap(size int, min bool) *Heap
  • func NewMaxHeap(size int) *Heap
  • func NewMinHeap(size int) *Heap
  • func (h *Heap) Items() (it types.Iterator)
  • func (h *Heap) MaxHeap() bool
  • func (h *Heap) MinHeap() bool
  • func (h *Heap) Peek() interface{}
  • func (h *Heap) Pop() interface{}
  • func (h *Heap) Push(priority int, item interface{})
  • func (h *Heap) Size() int
  • func (h *Heap) Verify() error
• type PriorityQueue
• type UniquePQ
  • func NewUnique(pq PriorityQueue) *UniquePQ
  • func (u *UniquePQ) Add(priority int, item types.Hashable)
  • func (u *UniquePQ) Peek() interface{}
  • func (u *UniquePQ) Pop() interface{}
  • func (u *UniquePQ) Push(priority int, item interface{})
  • func (u *UniquePQ) Size() int

Types

type Heap

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

A binary heap for Priority Queues. The priorities are modeled explicitly as integers. It can work either as a min heap or a max heap.

func NewHeap

func NewHeap(size int, min bool) *Heap

Make a new binary heap. size : hint for the size of the heap

(should estimate the maximal size)

min : false == max heap, true == min heap

func NewMaxHeap

func NewMaxHeap(size int) *Heap

func NewMinHeap

func NewMinHeap(size int) *Heap

func (*Heap) Items

func (h *Heap) Items() (it types.Iterator)

func (*Heap) MaxHeap

func (h *Heap) MaxHeap() bool

Is this a max heap?

func (*Heap) MinHeap

func (h *Heap) MinHeap() bool

Is this a min heap?

func (*Heap) Peek

func (h *Heap) Peek() interface{}

Peek at the highest (or lowest) priority item

func (*Heap) Pop

func (h *Heap) Pop() interface{}

Pop the highest (or lowest) priority item

func (*Heap) Push

func (h *Heap) Push(priority int, item interface{})

Push an item with a priority

func (*Heap) Size

func (h *Heap) Size() int

How many items in the heap?

func (*Heap) Verify

func (h *Heap) Verify() error

Verify the heap is properly structured.

type PriorityQueue

type PriorityQueue interface {
	types.Sized
	Push(priority int, item interface{})
	Peek() interface{}
	Pop() interface{}
}

type UniquePQ

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

This priority queue only allows unique entries. Internally this is implemented using a Hash set. All items added must be types.Hashable

func NewUnique

func NewUnique(pq PriorityQueue) *UniquePQ

Construct a new unique priority queue using the provided priority queue.

func (*UniquePQ) Add

func (u *UniquePQ) Add(priority int, item types.Hashable)

Add an item to the priority queue. It must be hashable.

func (*UniquePQ) Peek

func (u *UniquePQ) Peek() interface{}

Get the top element

func (*UniquePQ) Pop

func (u *UniquePQ) Pop() interface{}

Get and remove the top element

func (*UniquePQ) Push

func (u *UniquePQ) Push(priority int, item interface{})

This method is provided so it implements the PriorityQueue interface. In reality item must be types.Hashable. The implementation simply does a type assertion on item and calls Add.

func (*UniquePQ) Size

func (u *UniquePQ) Size() int

How many items in the queue?