heap

package

v0.6.2 Latest Latest Go to latest Published: Jul 18, 2022 License: BSD-3-Clause Imports: 4 Imported by: 3

Details

Valid go.mod file
Redistributable license
Tagged version
Stable version
Learn more about best practices

Repository

github.com/timtadh/data-structures

Links

Open Source Insights

Documentation ¶

Index ¶

type Heap
type PriorityQueue
type UniquePQ
- func NewUnique(pq PriorityQueue) *UniquePQ

Constants ¶

This section is empty.

Variables ¶

This section is empty.

Functions ¶

This section is empty.

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?

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL