Documentation
¶
Overview ¶
Package queue provides a generic priority queue implementation optimized for external sorting. It uses Go's container/heap package internally to maintain heap properties efficiently. The priority queue supports any type E with a user-provided comparison function.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PriorityQueue ¶
type PriorityQueue[E any] struct { // contains filtered or unexported fields }
PriorityQueue is a generic priority queue that maintains elements in sorted order according to a user-provided comparison function. It provides efficient O(log n) insertion and removal of the minimum/maximum element. This implementation is specifically optimized for the external sorting use case where elements need to be efficiently merged from multiple sorted streams.
func NewPriorityQueue ¶
func NewPriorityQueue[E any](cmpFunc func(E, E) int) *PriorityQueue[E]
NewPriorityQueue creates a new priority queue with the given comparison function. The cmpFunc should return a negative integer if the first argument should have higher priority (appear earlier) than the second argument, zero if they are equal, and a positive integer if the first should appear later. For ascending order, use cmp.Compare(a, b). The queue starts empty and elements can be added with Push().
func (*PriorityQueue[E]) Len ¶
func (pq *PriorityQueue[E]) Len() int
Len returns the current number of elements in the priority queue. This operation is O(1).
func (*PriorityQueue[E]) Peek ¶
func (pq *PriorityQueue[E]) Peek() E
Peek returns the highest priority element without removing it from the queue. This allows inspection of the next element that would be returned by Pop(). This operation is O(1). Panics if the queue is empty.
func (*PriorityQueue[E]) PeekUpdate ¶
func (pq *PriorityQueue[E]) PeekUpdate()
PeekUpdate must be called after modifying the value returned by Peek() in-place. This re-establishes the heap property when the priority of the top element changes. This is more efficient than Pop() followed by Push() when updating the top element. This operation is O(log n).
func (*PriorityQueue[E]) Pop ¶
func (pq *PriorityQueue[E]) Pop() E
Pop removes and returns the highest priority element from the queue. The returned element is the one that would be returned by Peek(). This operation is O(log n). Panics if the queue is empty.
func (*PriorityQueue[E]) Print ¶
func (pq *PriorityQueue[E]) Print()
Print outputs the current contents of the priority queue to stdout. Note that elements are printed in heap order, not priority order. This method is primarily intended for debugging purposes.
func (*PriorityQueue[E]) Push ¶
func (pq *PriorityQueue[E]) Push(x E)
Push adds a new element to the priority queue, maintaining heap properties. The element will be positioned according to the comparison function provided during queue creation. This operation is O(log n).
Source Files