heap

Documentation

Index

• func Empty[A any, B comparable](h Heap[A, B]) bool
• 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], currentA, newA *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](bExtractor func(*A) B) Heap[A, B]

Functions

func Empty

func Empty[A any, B comparable](h Heap[A, B]) bool

Determines if given heap is empty.

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

Returns - Whether or not the heap is empty Performance - O(1)

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], currentA, newA *A, lt func(l, r *A) bool) Heap[A, B]

Replaces the currentA element in the heap with the newA element, moving it up or down so as to maintain the heap property of a parent always being less than or equal to all its children. Parameters:

h - the generic heap object containing the heap(represented as a slice) and the reverse-lookup map.
currentA - the heap element you want to replace
newA - the heap element you are replacing currentA with
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 with the currentA element replaced by the newA element and with the newA element
in its proper place in the heap.  Its up to the caller to ensure the currentA and newA are the same except for the key.

Performance - O(log N)

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](bExtractor func(*A) B) Heap[A, B]