priorityqueue

Documentation

Index

• type BiDirTreeNode
• type BinomialHeap
  • func (b *BinomialHeap) DeleteMin() (int, error)
  • func (b *BinomialHeap) Empty() bool
  • func (b *BinomialHeap) Insert(x int) DataNode
  • func (b *BinomialHeap) Meld(other MeldablePQ) error
  • func (b *BinomialHeap) Min() (int, error)
• type CompletePQ
• type DataNode
• type FibonacciHeap
  • func (f *FibonacciHeap) DecreaseKey(target DataNode, key int) error
  • func (f *FibonacciHeap) Delete(target DataNode) (int, error)
  • func (f *FibonacciHeap) DeleteMin() (int, error)
  • func (f *FibonacciHeap) Empty() bool
  • func (f *FibonacciHeap) Insert(x int) DataNode
  • func (f *FibonacciHeap) Meld(other MeldablePQ) error
  • func (f *FibonacciHeap) Min() (int, error)
• type MeldablePQ
• type PriorityQueue

Types

type BiDirTreeNode

type BiDirTreeNode interface {
	DataNode
	Next() BiDirTreeNode
	Prev() BiDirTreeNode
	SetNext(n BiDirTreeNode)
	SetPrev(n BiDirTreeNode)
	AddChild(ch BiDirTreeNode)
}

BiDirTreeNode defines operations of bidirectional linked-list node, which supports getting/setting next/prev node, and add new node to the children list

type BinomialHeap

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

BinomialHeap implementation that is introduced in 'Fundamentals of Data Structures in C'

func (*BinomialHeap) DeleteMin

func (b *BinomialHeap) DeleteMin() (int, error)

DeleteMin pops the minimum from the BinomialHeap then returns it, error if the heap is empty.

Amortized cost is O(lg n).

func (*BinomialHeap) Empty

func (b *BinomialHeap) Empty() bool

Empty returns whether the heap is empty or not.

func (*BinomialHeap) Insert

func (b *BinomialHeap) Insert(x int) DataNode

Insert x into the BinomialHeap and return the inserted node.

Amortized cost is O(1).

func (*BinomialHeap) Meld

func (b *BinomialHeap) Meld(other MeldablePQ) error

Meld two BinomialHeap and leave other empty, error if the underlying type of other is not BinomialHeap.

Amortized cost is O(1).

func (*BinomialHeap) Min

func (b *BinomialHeap) Min() (int, error)

Min peeks and returns the minimum of the heap.

type CompletePQ

type CompletePQ interface {
	MeldablePQ
	Delete(target DataNode) (int, error)
	DecreaseKey(target DataNode, key int) error
}

type DataNode

type DataNode interface {
	Data() int
}

DataNode exposes only one API, which returns the contained data

type FibonacciHeap

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

FibonacciHeap implementation that is introduced in 'Fundamentals of Data Structures in C'

func (*FibonacciHeap) DecreaseKey

func (f *FibonacciHeap) DecreaseKey(target DataNode, key int) error

DecreaseKey decrease the key of the specified node in f, error if key is greater than original key or the target's type is incorrect.

Amortized cost is O(1).

func (*FibonacciHeap) Delete

func (f *FibonacciHeap) Delete(target DataNode) (int, error)

Delete the specified arbitrary node in the FibonacciHeap f, error if f is empty or the target's type is incorrect.

Amortized cost is O(lg n).

func (*FibonacciHeap) DeleteMin

func (f *FibonacciHeap) DeleteMin() (int, error)

DeleteMin pops the minimum from the FibonacciHeap then returns it, error if the heap is empty.

Amortized cost is O(lg n).

func (*FibonacciHeap) Empty

func (f *FibonacciHeap) Empty() bool

Empty returns whether the heap is empty or not.

func (*FibonacciHeap) Insert

func (f *FibonacciHeap) Insert(x int) DataNode

Insert x into the FibonacciHeap and return the inserted node.

Amortized cost is O(1).

func (*FibonacciHeap) Meld

func (f *FibonacciHeap) Meld(other MeldablePQ) error

Meld two FibonacciHeap and leave other empty, error if the underlying type of other is not FibonacciHeap.

Amortized cost is O(1).

func (*FibonacciHeap) Min

func (f *FibonacciHeap) Min() (int, error)

Min peeks and returns the minimum of the heap.

type MeldablePQ

type MeldablePQ interface {
	PriorityQueue
	Meld(other MeldablePQ) error
}

type PriorityQueue

type PriorityQueue interface {
	Empty() bool
	Insert(x int) DataNode
	DeleteMin() (int, error)
	Min() (int, error)
}