Documentation
¶
Index ¶
- type Box
- type Hash
- type Iterable
- type Iterator
- type Map
- type MapEntry
- type PriorityQueue
- func (p *PriorityQueue[T]) Add(element T) T
- func (p *PriorityQueue[T]) Clear()
- func (p *PriorityQueue[T]) InsertWithOverflow(element T) T
- func (p *PriorityQueue[T]) Iterator() iter.Seq[T]
- func (p *PriorityQueue[T]) Pop() (T, error)
- func (p *PriorityQueue[T]) Remove(element T) bool
- func (p *PriorityQueue[T]) SetSize(size int)
- func (p *PriorityQueue[T]) Size() int
- func (p *PriorityQueue[T]) Top() T
- func (p *PriorityQueue[T]) UpdateTop() T
- func (p *PriorityQueue[T]) UpdateTopByNewTop(newTop T) T
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PriorityQueue ¶
type PriorityQueue[T any] struct { // contains filtered or unexported fields }
func NewPriorityQueue ¶
func NewPriorityQueue[T any](maxSize int, lessThan func(a, b T) bool) *PriorityQueue[T]
func NewPriorityQueueV1 ¶
func NewPriorityQueueV1[T any](maxSize int, supplier func() T, lessThan func(a, b T) bool) *PriorityQueue[T]
func (*PriorityQueue[T]) Add ¶
func (p *PriorityQueue[T]) Add(element T) T
Add Adds an Object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize an ArrayIndexOutOfBoundsException is thrown. Returns: the new 'top' element in the queue.
func (*PriorityQueue[T]) Clear ¶
func (p *PriorityQueue[T]) Clear()
Clear Removes all entries from the PriorityQueue.
func (*PriorityQueue[T]) InsertWithOverflow ¶
func (p *PriorityQueue[T]) InsertWithOverflow(element T) T
InsertWithOverflow Adds an Object to a PriorityQueue in log(size) time. It returns the object (if any) that was dropped off the heap because it was full. This can be the given parameter (in case it is smaller than the full heap's minimum, and couldn't be added), or another object that was previously the smallest value in the heap and now has been replaced by a larger one, or null if the queue wasn't yet full with maxSize elements.
func (*PriorityQueue[T]) Iterator ¶
func (p *PriorityQueue[T]) Iterator() iter.Seq[T]
func (*PriorityQueue[T]) Pop ¶
func (p *PriorityQueue[T]) Pop() (T, error)
Pop Removes and returns the least element of the PriorityQueue in log(size) time.
func (*PriorityQueue[T]) Remove ¶
func (p *PriorityQueue[T]) Remove(element T) bool
Remove Removes an existing element currently stored in the PriorityQueue. Cost is linear with the size of the queue.
(A specialization of PriorityQueue which tracks element positions would provide a constant remove time but the trade-off would be extra cost to all additions/insertions)
func (*PriorityQueue[T]) SetSize ¶
func (p *PriorityQueue[T]) SetSize(size int)
func (*PriorityQueue[T]) Size ¶
func (p *PriorityQueue[T]) Size() int
Size Returns the number of elements currently stored in the PriorityQueue.
func (*PriorityQueue[T]) Top ¶
func (p *PriorityQueue[T]) Top() T
Top Returns the least element of the PriorityQueue in constant time.
func (*PriorityQueue[T]) UpdateTop ¶
func (p *PriorityQueue[T]) UpdateTop() T
UpdateTop Should be called when the Object at top changes values. Still log(n) worst case, but it's at least twice as fast to
pq.top().change(); pq.updateTop();
instead of
o = pq.pop(); o.change(); pq.push(o);
Returns: the new 'top' element.
func (*PriorityQueue[T]) UpdateTopByNewTop ¶
func (p *PriorityQueue[T]) UpdateTopByNewTop(newTop T) T
UpdateTopByNewTop Replace the top of the pq with newTop and run updateTop().
Source Files