heap

Imports

Imports #

"sort"

Interfaces

Interface interface #

The Interface type describes the requirements for a type using the routines in this package. Any type that implements it may be used as a min-heap with the following invariants (established after [Init] has been called or if the data is empty or sorted): !h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len() Note that [Push] and [Pop] in this interface are for package heap's implementation to call. To add and remove things from the heap, use [heap.Push] and [heap.Pop].

type Interface interface {
sort.Interface
Push(x any)
Pop() any
}

Functions

Fix function #

Fix re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling [Remove](h, i) followed by a Push of the new value. The complexity is O(log n) where n = h.Len().

func Fix(h Interface, i int)

Init function #

Init establishes the heap invariants required by the other routines in this package. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. The complexity is O(n) where n = h.Len().

func Init(h Interface)

Pop function #

Pop removes and returns the minimum element (according to Less) from the heap. The complexity is O(log n) where n = h.Len(). Pop is equivalent to [Remove](h, 0).

func Pop(h Interface) any

Push function #

Push pushes the element x onto the heap. The complexity is O(log n) where n = h.Len().

func Push(h Interface, x any)

Remove function #

Remove removes and returns the element at index i from the heap. The complexity is O(log n) where n = h.Len().

func Remove(h Interface, i int) any

down function #

func down(h Interface, i0 int, n int) bool

up function #

func up(h Interface, j int)

Generated with Arrow