Documentation
¶
Overview ¶
Package priorityqueue implements a generic priority queue data structure.
PriorityQueue is a heap-based priority queue that supports both min-heap and max-heap modes. It allows insertion of elements and retrieval of the highest priority element in O(log n) time.
Features:
- Supports min-heap and max-heap modes
- Efficient insertion and retrieval operations with O(log n) time complexity
- Supports peeking at the highest priority element without removal
- Supports clearing operation
Usage examples:
// Create a min-heap (sorted by age)
minHeap := priorityqueue.NewMinPriorityQueue[Person](func(a, b Person) int {
return a.Age - b.Age
})
// Add elements
minHeap.Push(Person{Name: "Charlie", Age: 35})
minHeap.Push(Person{Name: "Alice", Age: 25})
minHeap.Push(Person{Name: "Bob", Age: 30})
// Get elements by priority
for !minHeap.IsEmpty() {
person, _ := minHeap.Pop()
fmt.Printf("%s (Age: %d)\n", person.Name, person.Age)
}
Index ¶
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 }
PriorityQueue is a heap-based priority queue
func NewMax ¶
func NewMax[T any](cmp func(T, T) int) *PriorityQueue[T]
NewMax creates a new max-heap priority queue
Parameters:
- cmp: comparison function that returns negative when a < b, zero when a == b, and positive when a > b
Return value:
- Newly created max-heap priority queue instance
Max-heap property: largest element has highest priority
Time complexity: O(1)
func NewMaxOrdered ¶
func NewMaxOrdered[T cmp.Ordered]() *PriorityQueue[T]
NewMaxOrdered creates a new max-heap priority queue with ordered elements
Type Parameters:
- T: Element type, must be ordered
Return value:
- Newly created max-heap priority queue instance with ordered elements
Max-heap property: largest element has highest priority
Time complexity: O(1)
func NewMin ¶
func NewMin[T any](cmp func(T, T) int) *PriorityQueue[T]
NewMin creates a new min-heap priority queue
Parameters:
- cmp: comparison function that returns negative when a < b, zero when a == b, and positive when a > b
Return value:
- Newly created min-heap priority queue instance
Min-heap property: smallest element has highest priority
Time complexity: O(1)
func NewMinOrdered ¶
func NewMinOrdered[T cmp.Ordered]() *PriorityQueue[T]
NewMinOrdered creates a new min-heap priority queue with ordered elements
Type Parameters:
- T: Element type, must be ordered
Return value:
- Newly created min-heap priority queue instance with ordered elements
Min-heap property: smallest element has highest priority
Time complexity: O(1)
func (*PriorityQueue[T]) Clear ¶
func (pq *PriorityQueue[T]) Clear()
Clear clears the priority queue
Time complexity: O(1)
func (*PriorityQueue[T]) IsEmpty ¶
func (pq *PriorityQueue[T]) IsEmpty() bool
IsEmpty checks if the priority queue is empty
Returns:
- true if the queue is empty, false otherwise
Time complexity: O(1)
func (*PriorityQueue[T]) Len ¶
func (pq *PriorityQueue[T]) Len() int
Len returns the number of elements in the priority queue
Returns:
- The number of elements in the queue
Time complexity: O(1)
func (*PriorityQueue[T]) Peek ¶
func (pq *PriorityQueue[T]) Peek() (T, bool)
Peek returns the element with the highest priority (heap top) but does not remove it
Returns:
- If the queue is not empty, returns the element with the highest priority and true
- If the queue is empty, returns the zero value of type T and false
Time complexity: O(1)
func (*PriorityQueue[T]) Pop ¶
func (pq *PriorityQueue[T]) Pop() (T, bool)
Pop removes and returns the element with the highest priority (heap top)
Returns:
- If the queue is not empty, returns the element with the highest priority and true
- If the queue is empty, returns the zero value of type T and false
Time complexity: O(log n)
func (*PriorityQueue[T]) Push ¶
func (pq *PriorityQueue[T]) Push(value T)
Push adds an element to the priority queue
Parameters:
- value: The value to add to the queue
Time complexity: O(log n)
Source Files