pairing

Documentation

Overview

Package pairing implements a Pairing heap Data structure

Structure is not thread safe.

Reference: https://en.wikipedia.org/wiki/Pairing_heap

Index

• type PairHeap
  • func New() *PairHeap
  • func (p *PairHeap) Adjust(item, new heap.Item) heap.Item
  • func (p *PairHeap) Clear()
  • func (p *PairHeap) Delete(item heap.Item) heap.Item
  • func (p *PairHeap) DeleteMin() heap.Item
  • func (p *PairHeap) Do(it heap.ItemIterator)
  • func (p *PairHeap) Find(item heap.Item) heap.Item
  • func (p *PairHeap) FindMin() heap.Item
  • func (p *PairHeap) Init() *PairHeap
  • func (p *PairHeap) Insert(item heap.Item) heap.Item
  • func (p *PairHeap) IsEmpty() bool
  • func (p *PairHeap) Meld(a heap.Interface) heap.Interface

Types

type PairHeap

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

PairHeap is an implementation of a Pairing Heap. The zero value for PairHeap Root is an empty Heap.

func New

func New() *PairHeap

New returns an initialized PairHeap.

func (*PairHeap) Adjust

func (p *PairHeap) Adjust(item, new heap.Item) heap.Item

Adjusts the value to the node item and returns it The complexity is O(n) amortized.

func (*PairHeap) Clear

func (p *PairHeap) Clear()

Resets the current PairHeap

func (*PairHeap) Delete

func (p *PairHeap) Delete(item heap.Item) heap.Item

Deletes a node from the heap and returns the item The complexity is O(log n) amortized.

func (*PairHeap) DeleteMin

func (p *PairHeap) DeleteMin() heap.Item

DeleteMin removes the top most value from the PairHeap and returns it The complexity is O(log n) amortized.

func (*PairHeap) Do

func (p *PairHeap) Do(it heap.ItemIterator)

Do calls function cb on each element of the PairingHeap, in order of appearance. The behavior of Do is undefined if cb changes *p.

func (*PairHeap) Find

func (p *PairHeap) Find(item heap.Item) heap.Item

Exhausting search of the element that matches item and returns it The complexity is O(n) amortized.

func (*PairHeap) FindMin

func (p *PairHeap) FindMin() heap.Item

Find the smallest item in the priority queue. The complexity is O(1).

func (*PairHeap) Init

func (p *PairHeap) Init() *PairHeap

Init initializes or clears the PairHeap

func (*PairHeap) Insert

func (p *PairHeap) Insert(item heap.Item) heap.Item

Inserts the value to the PairHeap and returns the item The complexity is O(1).

func (*PairHeap) IsEmpty

func (p *PairHeap) IsEmpty() bool

IsEmpty returns true if PairHeap p is empty. The complexity is O(1).

func (*PairHeap) Meld

func (p *PairHeap) Meld(a heap.Interface) heap.Interface

Return the heap formed by taking the union of the item disjoint current heap and a that is of the same type