Documentation
¶
Overview ¶
Package pqueue provides OOP-style priority queues.
For better performance, all functions in this package are unsafe for concurrency unless otherwise specified.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PriorityQueue ¶
type PriorityQueue[Item any] interface { container.Container[Item] // Cap returns the current capacity of the queue. Cap() int // Enqueue adds items x into the queue. // // Time complexity: O(m log(m + n)), where m = len(x), n = pq.Len(). Enqueue(x ...Item) // Dequeue removes and returns the highest-priority item in the queue. // // It panics if the queue is nil or empty. // // Time complexity: O(log n), where n = pq.Len(). Dequeue() Item // Top returns the highest-priority item in the queue, // without modifying the queue. // // It panics if the queue is nil or empty. // // Time complexity: O(1). Top() Item // ReplaceTop replaces the highest-priority item with newX and // returns the current highest-priority item. // // It panics if the queue is nil or empty. // // Time complexity: O(log n), where n = pq.Len(). ReplaceTop(newX Item) Item // Clear removes all items in the queue and asks to release the memory. Clear() }
PriorityQueue is an interface representing a priority queue.
Its method Range may not access items in a priority-related order. It only guarantees that each item is accessed once.
func New ¶
func New[Item any]( lessFn compare.LessFunc[Item], data container.Container[Item], ) PriorityQueue[Item]
New creates a new priority queue. In this priority queue, the smaller the item (compared by the function lessFn), the higher its priority.
lessFn is a function to report whether a < b. It must describe a transitive ordering:
- if both lessFn(a, b) and lessFn(b, c) are true, then lessFn(a, c) must be true as well.
- if both lessFn(a, b) and lessFn(b, c) are false, then lessFn(a, c) must be false as well.
Note that floating-point comparison (the < operator on float32 or float64 values) is not a transitive ordering when not-a-number (NaN) values are involved.
data is the initial items added to the queue.
It panics if lessFn is nil.
Source Files