heap

Documentation

Index

• func Fix[S ~[]E, E cmp.Ordered](h S, i int)
• func Heapify[S ~[]E, E cmp.Ordered](h S)
• func Pop[S ~[]E, E cmp.Ordered](h S) (S, E)
• func Push[S ~[]E, E cmp.Ordered](h S, x E) S
• func Remove[S ~[]E, E cmp.Ordered](h S, i int) (S, E)
• type Item
• type PriorityQueue
  • func (pq PriorityQueue[T]) Len() int
  • func (pq PriorityQueue[T]) Less(i, j int) bool
  • func (pq *PriorityQueue[T]) Pop() any
  • func (pq *PriorityQueue[T]) Push(x any)
  • func (pq PriorityQueue[T]) Swap(i, j int)

Functions

func Fix

func Fix[S ~[]E, E cmp.Ordered](h S, i int)

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 Heapify

func Heapify[S ~[]E, E cmp.Ordered](h S)

Heapify 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.

func Pop

func Pop[S ~[]E, E cmp.Ordered](h S) (S, E)

Pop removes and returns the minimum element (according to Less) from the heap. Pop is equivalent to Remove(h, 0).

func Push

func Push[S ~[]E, E cmp.Ordered](h S, x E) S

Push pushes the element x onto the heap.

func Remove

func Remove[S ~[]E, E cmp.Ordered](h S, i int) (S, E)

Remove removes and returns the element at index i from the heap.

Types

type Item

type Item[T any] struct {
	// contains filtered or unexported fields
}

type PriorityQueue

type PriorityQueue[T any] []*Item[T]

A PriorityQueue implements heap.Interface and holds Items.

func (PriorityQueue[T]) Len

func (pq PriorityQueue[T]) Len() int

func (PriorityQueue[T]) Less

func (pq PriorityQueue[T]) Less(i, j int) bool

func (*PriorityQueue[T]) Pop

func (pq *PriorityQueue[T]) Pop() any

func (*PriorityQueue[T]) Push

func (pq *PriorityQueue[T]) Push(x any)

func (PriorityQueue[T]) Swap

func (pq PriorityQueue[T]) Swap(i, j int)