heapx

Documentation

Index

• type Heap
  • func NewHeap[T any](cmp LessFunc[T]) *Heap[T]
  • func (h *Heap[T]) Len() int
  • func (h *Heap[T]) Peek() (x T, ok bool)
  • func (h *Heap[T]) Pop() (x T, ok bool)
  • func (h *Heap[T]) Push(x T)
• type LessFunc
• type Ordered
• type PriorityQueue
  • func NewMaxPriorityQueue[P Ordered, V any]() *PriorityQueue[P, V]
  • func NewMinPriorityQueue[P Ordered, V any]() *PriorityQueue[P, V]
  • func (pq *PriorityQueue[P, V]) Len() int
  • func (pq *PriorityQueue[P, V]) Peek() (priority P, value V, ok bool)
  • func (pq *PriorityQueue[P, V]) Pop() (priority P, value V, ok bool)
  • func (pq *PriorityQueue[P, V]) Push(priority P, value V)

Types

type Heap

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

Heap implements the classic heap data-structure. A Heap is not safe for concurrent operations.

func NewHeap

func NewHeap[T any](cmp LessFunc[T]) *Heap[T]

NewHeap creates a new Heap.

func (*Heap[T]) Len

func (h *Heap[T]) Len() int

Len returns the size of the heap.

func (*Heap[T]) Peek

func (h *Heap[T]) Peek() (x T, ok bool)

Peek returns the minium element (according to the LessFunc) in the heap, it does not remove the item from the heap. The complexity is O(1).

func (*Heap[T]) Pop

func (h *Heap[T]) Pop() (x T, ok bool)

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

func (*Heap[T]) Push

func (h *Heap[T]) Push(x T)

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

type LessFunc

type LessFunc[T any] func(lhs, rhs T) bool

LessFunc is a comparator function to build a Heap.

type Ordered

type Ordered interface {
	constraints.Integer | ~string
}

type PriorityQueue

type PriorityQueue[P Ordered, V any] struct {
	// contains filtered or unexported fields
}

PriorityQueue is a heap-based priority queue implementation.

It can be either min (ascending) or max (descending) oriented/ordered. The type parameters `P` and `V` specify the type of the underlying priority and value.

A PriorityQueue is not safe for concurrent operations.

func NewMaxPriorityQueue

func NewMaxPriorityQueue[P Ordered, V any]() *PriorityQueue[P, V]

NewMaxPriorityQueue creates a new maximum oriented PriorityQueue.

func NewMinPriorityQueue

func NewMinPriorityQueue[P Ordered, V any]() *PriorityQueue[P, V]

NewMinPriorityQueue creates a new minimum oriented PriorityQueue.

func (*PriorityQueue[P, V]) Len

func (pq *PriorityQueue[P, V]) Len() int

Len returns the size of the PriorityQueue.

func (*PriorityQueue[P, V]) Peek

func (pq *PriorityQueue[P, V]) Peek() (priority P, value V, ok bool)

Peek returns the most priority value in the PriorityQueue, it does not remove the value from the queue.

func (*PriorityQueue[P, V]) Pop

func (pq *PriorityQueue[P, V]) Pop() (priority P, value V, ok bool)

Pop removes and returns the most priority value in the PriorityQueue.

func (*PriorityQueue[P, V]) Push

func (pq *PriorityQueue[P, V]) Push(priority P, value V)

Push adds a value with priority to the PriorityQueue.