data-structures: github.com/timtadh/data-structures/heap Index | Files

package heap

import "github.com/timtadh/data-structures/heap"

Index

Package Files

pq.go unique.go

type Heap Uses

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 Uses

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 Uses

func NewMaxHeap(size int) *Heap

func NewMinHeap Uses

func NewMinHeap(size int) *Heap

func (*Heap) Items Uses

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

func (*Heap) MaxHeap Uses

func (h *Heap) MaxHeap() bool

Is this a max heap?

func (*Heap) MinHeap Uses

func (h *Heap) MinHeap() bool

Is this a min heap?

func (*Heap) Peek Uses

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

Peek at the highest (or lowest) priority item

func (*Heap) Pop Uses

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

Pop the highest (or lowest) priority item

func (*Heap) Push Uses

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

Push an item with a priority

func (*Heap) Size Uses

func (h *Heap) Size() int

How many items in the heap?

func (*Heap) Verify Uses

func (h *Heap) Verify() error

Verify the heap is properly structured.

type PriorityQueue Uses

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

type UniquePQ Uses

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 Uses

func NewUnique(pq PriorityQueue) *UniquePQ

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

func (*UniquePQ) Add Uses

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

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

func (*UniquePQ) Peek Uses

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

Get the top element

func (*UniquePQ) Pop Uses

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

Get and remove the top element

func (*UniquePQ) Push Uses

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 Uses

func (u *UniquePQ) Size() int

How many items in the queue?

Package heap imports 4 packages (graph). Updated 2017-05-31. Refresh now. Tools for package owners.