Documentation
¶
Index ¶
- func Fix[T any](h Interface[T], i int)
- func Init[T any](h Interface[T])
- func Pop[T any](h Interface[T]) any
- func Push[T any](h Interface[T], x T)
- func Remove[T any](h Interface[T], i int) any
- type Element
- type Heap
- func (h *Heap[T]) Fix(e *Element[T])
- func (h *Heap[T]) Init(s []T, cmp func(T, T) bool)
- func (h *Heap[T]) Len() int
- func (h *Heap[T]) Peek() *Element[T]
- func (h *Heap[T]) Pop() *Element[T]
- func (h *Heap[T]) PopAll() iter.Seq[T]
- func (h *Heap[T]) Push(x T) *Element[T]
- func (h *Heap[T]) PushElement(e *Element[T])
- func (h *Heap[T]) Remove(e *Element[T])
- type Interface
- type Slice
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Fix ¶
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 Init ¶
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 Pop ¶
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).
Types ¶
type Heap ¶
type Heap[T any] struct { // contains filtered or unexported fields }
func (*Heap[T]) Peek ¶
Peek returns the minimum element (according to compare function) from the heap without removing it.
func (*Heap[T]) Pop ¶
Pop removes and returns the minimum element (according to compare function) from the heap.
func (*Heap[T]) PushElement ¶
PushElement pushes the element e onto the heap.
type Interface ¶
type Interface[T any] interface { sort.Interface Push(x T) // add x as element Len() Pop() T // remove and return element Len() - 1. }
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 Slice ¶
type Slice[T any] struct { Values []T // contains filtered or unexported fields }
func (*Slice[T]) Fix ¶
Fix re-establishes the heap ordering after the element at index i has changed its value.
func (*Slice[T]) Peek ¶
Peek returns the minimum element (according to compare function) from the heap without removing it.
func (*Slice[T]) Pop ¶
Pop removes and returns the minimum element (according to compare function) from the heap.
Source Files