Documentation
¶
Overview ¶
Package xheap contains extensions to the standard library package container/heap.
Index ¶
- type Heap
- type KP
- type PriorityQueue
- func (h *PriorityQueue[K, P]) Contains(k K) bool
- func (h *PriorityQueue[K, P]) Grow(n int)
- func (h *PriorityQueue[K, P]) Iterate() iterator.Iterator[K]
- func (h *PriorityQueue[K, P]) Len() int
- func (h *PriorityQueue[K, P]) Peek() K
- func (h *PriorityQueue[K, P]) Pop() K
- func (h *PriorityQueue[K, P]) Priority(k K) P
- func (h *PriorityQueue[K, P]) Remove(k K)
- func (h *PriorityQueue[K, P]) Update(k K, p P)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap[T any] struct { // contains filtered or unexported fields }
Heap is a min-heap (https://en.wikipedia.org/wiki/Binary_heap). Min-heaps are a collection structure that provide constant-time access to the minimum element, and logarithmic-time removal. They are most commonly used as a priority queue.
Push and Pop take amortized O(log(n)) time where n is the number of items in the heap.
Len and Peek take O(1) time.
func New ¶
New returns a new Heap which uses less to determine the minimum element.
The elements from initial are added to the heap. initial is modified by New and utilized by the Heap, so it should not be used after passing to New(). Passing initial is faster (O(n)) than creating an empty heap and pushing each item (O(n * log(n))).
func (*Heap[T]) Grow ¶
Grow allocates sufficient space to add n more elements without needing to reallocate.
func (*Heap[T]) Iterate ¶
Iterate iterates over the elements of the heap.
The iterator panics if the heap has been modified since iteration started.
func (*Heap[T]) Peek ¶
func (h *Heap[T]) Peek() T
Peek returns the minimum item in the heap. It panics if h.Len()==0.
type PriorityQueue ¶
type PriorityQueue[K comparable, P any] struct { // contains filtered or unexported fields }
PriorityQueue is a queue that yields items in increasing order of priority.
func NewPriorityQueue ¶
func NewPriorityQueue[K comparable, P any]( less xsort.Less[P], initial []KP[K, P], ) PriorityQueue[K, P]
NewPriorityQueue returns a new PriorityQueue which uses less to determine the minimum element.
The elements from initial are added to the priority queue. initial is modified by NewPriorityQueue and utilized by the PriorityQueue, so it should not be used after passing to NewPriorityQueue. Passing initial is faster (O(n)) than creating an empty priority queue and pushing each item (O(n * log(n))).
Pop, Remove, and Update all take amortized O(log(n)) time where n is the number of items in the queue.
Len, Peek, Contains, and Priority take O(1) time.
func (*PriorityQueue[K, P]) Contains ¶
func (h *PriorityQueue[K, P]) Contains(k K) bool
Contains returns true if the given key is present in the priority queue.
func (*PriorityQueue[K, P]) Grow ¶
func (h *PriorityQueue[K, P]) Grow(n int)
Grow allocates sufficient space to add n more elements without needing to reallocate.
func (*PriorityQueue[K, P]) Iterate ¶
func (h *PriorityQueue[K, P]) Iterate() iterator.Iterator[K]
Iterate iterates over the elements of the priority queue.
The iterator panics if the priority queue has been modified since iteration started.
func (*PriorityQueue[K, P]) Len ¶
func (h *PriorityQueue[K, P]) Len() int
Len returns the current number of elements in the priority queue.
func (*PriorityQueue[K, P]) Peek ¶
func (h *PriorityQueue[K, P]) Peek() K
Peek returns the key of the lowest-P item in the priority queue. It panics if h.Len()==0.
func (*PriorityQueue[K, P]) Pop ¶
func (h *PriorityQueue[K, P]) Pop() K
Pop removes and returns the lowest-P item in the priority queue. It panics if h.Len()==0.
func (*PriorityQueue[K, P]) Priority ¶
func (h *PriorityQueue[K, P]) Priority(k K) P
Priority returns the priority of k, or the zero value of P if k is not present.
func (*PriorityQueue[K, P]) Remove ¶
func (h *PriorityQueue[K, P]) Remove(k K)
Remove removes the item with the given key if present.
func (*PriorityQueue[K, P]) Update ¶
func (h *PriorityQueue[K, P]) Update(k K, p P)
Update updates the priority of k to p, or adds it to the priority queue if not present.
Source Files