pairing

README

Pairing Priority Queue

Implementation Notes

Nodes contain the following:

• A key k, where k ∈ ℝ
• A pointer to a value
• A pointer to the parent
• A pointer to the next older sibling
• A pointer to the youngest child

Documentation

Index

• type Tree
  • func DecreaseKey[K cmp.Ordered, V any](t *Tree[K, V], targetNode *Tree[K, V], newKey K) *Tree[K, V]
  • func FindMin[K cmp.Ordered, V any](t *Tree[K, V]) *Tree[K, V]
  • func Insert[K cmp.Ordered, V any](t *Tree[K, V], new *Tree[K, V]) *Tree[K, V]
  • func Meld[K cmp.Ordered, V any](a, b *Tree[K, V]) *Tree[K, V]
  • func NewTree[K cmp.Ordered, V any](key K, value V) *Tree[K, V]
  • func RemoveMin[K cmp.Ordered, V any](t *Tree[K, V]) *Tree[K, V]
  • func (t *Tree[K, V]) Key() K
  • func (t *Tree[K, V]) Value() V

Types

type Tree

type Tree[K cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

func DecreaseKey

func DecreaseKey[K cmp.Ordered, V any](t *Tree[K, V], targetNode *Tree[K, V], newKey K) *Tree[K, V]

DecreaseKey decreases the target node's key to the provided new key. The new key must be less than the target node's current key.

func FindMin

func FindMin[K cmp.Ordered, V any](t *Tree[K, V]) *Tree[K, V]

FindMin returns the root node of the Tree, or nil if the Tree is empty.

func Insert

func Insert[K cmp.Ordered, V any](t *Tree[K, V], new *Tree[K, V]) *Tree[K, V]

Insert inserts a new node into a Tree.

func Meld

func Meld[K cmp.Ordered, V any](a, b *Tree[K, V]) *Tree[K, V]

Meld forms a new Tree from two other trees, with the largest becoming parent to the smallest.

func NewTree

func NewTree[K cmp.Ordered, V any](key K, value V) *Tree[K, V]

func RemoveMin

func RemoveMin[K cmp.Ordered, V any](t *Tree[K, V]) *Tree[K, V]

RemoveMin removes the root node (in other words, the smallest node) from the provided Tree, rebuilds the Tree, and returns the new root node.

func (*Tree[K, V]) Key

func (t *Tree[K, V]) Key() K

func (*Tree[K, V]) Value

func (t *Tree[K, V]) Value() V