binaryheap

Documentation

Overview

Package binaryheap provides a generic min-heap implementation.

Index

• type Heap
  • func New[T cmp.Ordered]() *Heap[T]
  • func NewWith[T comparable](comparator utils.Comparator[T]) *Heap[T]
  • func (heap *Heap[T]) Clear()
  • func (heap *Heap[T]) DeleteMin() (value T, ok bool)
  • func (heap *Heap[T]) FindMin() (value T, ok bool)
  • func (heap *Heap[T]) Insert(values ...T)
  • func (heap *Heap[T]) IsEmpty() bool
  • func (heap *Heap[T]) Size() int

Types

type Heap

type Heap[T comparable] struct {
	Comparator utils.Comparator[T]
	// contains filtered or unexported fields
}

Heap represents a min-heap data structure. It is implemented using a slice, where for any element at index i:

• Left child is at index 2*i + 1
• Right child is at index 2*i + 2
• Parent is at index (i-1)/2

func New

func New[T cmp.Ordered]() *Heap[T]

New creates a new min-heap for ordered types. It uses the natural ordering of the type.

func NewWith

func NewWith[T comparable](comparator utils.Comparator[T]) *Heap[T]

NewWith creates a new heap with a custom comparator. The comparator determines the heap ordering (min or max).

func (*Heap[T]) Clear

func (heap *Heap[T]) Clear()

Clear removes all elements from the heap.

func (*Heap[T]) DeleteMin

func (heap *Heap[T]) DeleteMin() (value T, ok bool)

DeleteMin removes and returns the minimum element from the heap. Returns (zero value, false) if the heap is empty.

func (*Heap[T]) FindMin

func (heap *Heap[T]) FindMin() (value T, ok bool)

FindMin returns the minimum element without removing it. Returns (zero value, false) if the heap is empty.

func (*Heap[T]) Insert

func (heap *Heap[T]) Insert(values ...T)

Insert adds one or more values to the heap. For a single value, it appends and percolates up. For multiple values, it uses Floyd's algorithm for O(n) heap construction.

func (*Heap[T]) IsEmpty

func (heap *Heap[T]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements.

func (*Heap[T]) Size

func (heap *Heap[T]) Size() int

Size returns the number of elements in the heap.