heap

Documentation

Index

• func FindMin[A any, B comparable](h Heap[A, B]) (*A, error)
• func FindPosition[A any, B comparable](h Heap[A, B], reverseKey B) int
• func ParentIdx(i int) int
• type Heap
  • func ChangeKey[A, B comparable](h Heap[A, B], currentKey, newKey *A, lt func(l, r *A) bool) Heap[A, B]
  • func HeapDelete[A any, B comparable](h Heap[A, B], i int, lt func(l, r *A) bool) (Heap[A, B], error)
  • func HeapInsert[A any, B comparable](h Heap[A, B], a *A, lt func(l, r *A) bool) Heap[A, B]
  • func New[A any, B comparable](keyExtractor func(*A) B) Heap[A, B]

Functions

func FindMin

func FindMin[A any, B comparable](h Heap[A, B]) (*A, error)

This is a pure function. Parameters:

h - the generic heap object containing the heap(represented as a slice) and the reverse-lookup map.

Returns -the minimum element in the given heap without removing it. O(1) Performance - O(1)

func FindPosition

func FindPosition[A any, B comparable](h Heap[A, B], reverseKey B) int

This is a pure function. Returns the position in the underylying heap array of the key value B from the reverdse-lookup map Parameters:

h - the generic heap object containing the heap(represented as a slice) and the reverse-lookup map.

Returns - the heap index(array index) of element with reverse key reverse key, or -1 if key does mot exist Performance - O(1)

func ParentIdx

func ParentIdx(i int) int

i int - the index in the given heap of the parent of element i. Array indices start with the number zero. Performance - O(1)

Types

type Heap

type Heap[A any, B comparable] struct {
	// contains filtered or unexported fields
}

A generic heap containing the heap's underlying array and a corresponding map that allows lookup of the key's index in the underlying array with O(1) cost. Also contains a function that allows extraction of the A's key value for insertion into the position map.

func ChangeKey

func ChangeKey[A, B comparable](h Heap[A, B], currentKey, newKey *A, lt func(l, r *A) bool) Heap[A, B]

TODO this is not complete and its API may change. And I have not tested it. Still fumbling around thinking about what I do with ther newKey

func HeapDelete

func HeapDelete[A any, B comparable](h Heap[A, B], i int, lt func(l, r *A) bool) (Heap[A, B], error)

Deletes an element from the given heap. This is not a pure function. Parameters:

h - the generic heap object containing the heap(represented as a slice) and the reverse-lookup map.
i int - the index into the heap of the element you want to delete. Array indices start with the number zero.
lt func(l, r A) bool - A predicate function that determines whether or not the left A element is less than the right A element.

Returns - The original heap that has the given element in its proper position.

If the heao is empty or the indice you are trying to delete is longer than the heap(zero indexed) then you get an error

Performance - O(log N)

func HeapInsert

func HeapInsert[A any, B comparable](h Heap[A, B], a *A, lt func(l, r *A) bool) Heap[A, B]

Inserts the given element into the given heap and returns the modified heap.

O(log n)

Parameters:

h - the generic heap object containing the heap(represented as a slice) and the reverse-lookup map.
a  A - the element you want to insert into the heap
lt func(l, r A) bool - A predicate function that determines whether or not the left A element is less than the right A element.

Returns - The original heap (as a slice) that has the given element in its proper position Performance - O(log N) NOTE This function assumes that the heap slice has no empty elements. It always adds a new one.

func New

func New[A any, B comparable](keyExtractor func(*A) B) Heap[A, B]