#Priority Queue
A priority queue is a data structure capable of maintaining maximum/minimum values at front of the queue, which may have other names in other programming languages (C++ std::priority_queue / Rust BinaryHeap ). The priority queue here is implemented as a pairing heap and has excellent performance.
#Usage
#Create
You can use PriorityQueue([]) or from_array() to create a priority queue.
///|
test {
let queue1 : @priority_queue.PriorityQueue[Int] = PriorityQueue([])
let queue2 = @priority_queue.from_array([1, 2, 3])
@json.json_inspect(queue1, content=[])
@json.json_inspect(queue2, content=[3, 2, 1])
}Note, however, that the default priority queue created is greater-first; if you need to create a less-first queue, you can write a struct belongs to Compare trait to implement it.
#Creating a Min-Heap with @cmp.Reverse
You can easily create a min-heap (smallest element first) using @cmp.Reverse to reverse the comparison order:
///|
test {
// Create a min-heap by wrapping elements with @cmp.Reverse
let min_heap = @priority_queue.from_array([
@cmp.Reverse(5),
Reverse(2),
Reverse(8),
Reverse(1),
])
// The smallest wrapped value (1) should be at the top
debug_inspect(min_heap.peek(), content="Some(Reverse(1))")
}#Length
You can use length() to get the number of elements in the current priority queue.
///|
test {
let pq = @priority_queue.from_array([1, 2, 3, 4, 5])
@test.assert_eq(pq.length(), 5)
}Similarly, you can use the is_empty to determine whether the priority queue is empty.
///|
test {
let pq : @priority_queue.PriorityQueue[Int] = PriorityQueue([])
@test.assert_eq(pq.is_empty(), true)
}#Peek
You can use peek() to look at the head element of a queue, which must be either the maximum or minimum value of an element in the queue, depending on the nature of the specification. The return value of peek() is an Option, which means that the result will be None when the queue is empty.
///|
test {
let pq = @priority_queue.from_array([1, 2, 3, 4, 5])
@test.assert_eq(pq.peek(), Some(5))
}#Push
You can use push() to add elements to the priority queue.
///|
test {
let pq : @priority_queue.PriorityQueue[Int] = PriorityQueue([])
pq.push(1)
pq.push(2)
@test.assert_eq(pq.peek(), Some(2))
}#Pop
You can use pop() to pop the element at the front of the priority queue, respectively, and like Peek, its return values are Option , loaded with the value of the element being popped.
///|
test {
let pq = @priority_queue.from_array([5, 4, 3, 2, 1])
@test.assert_eq(pq.pop(), Some(5))
}///|
test {
let pq = @priority_queue.from_array([5, 4, 3, 2, 1])
@test.assert_eq(pq.length(), 5)
}#Clear
You can use clear to clear a priority queue.
///|
test {
let pq = @priority_queue.from_array([1, 2, 3, 4, 5])
pq.clear()
@test.assert_eq(pq.is_empty(), true)
}#From Iterator
///|
test {
let pq = @priority_queue.from_iter(3, 1, 2)
@test.assert_eq(pq.peek(), Some(3))
}#Iterator & Conversion
iter() returns elements in descending priority order. to_array() collects them into an array.
///|
test {
let pq = @priority_queue.from_array([3, 1, 4, 1, 5])
let arr = pq.to_array()
// to_array returns elements sorted by priority (descending)
@debug.assert_eq(arr, [5, 4, 3, 1, 1])
}#Copy
copy() duplicates the heap structure: the copy gets its own nodes, so pushing to or popping from one queue does not affect the other. The stored elements themselves are not copied — both queues refer to the same values, so if the element type is mutable, mutating an element is observable through both queues.
///|
test {
let pq = @priority_queue.from_array([1, 2, 3])
let pq2 = pq.copy()
@test.assert_eq(pq2.pop(), Some(3))
@test.assert_eq(pq.length(), 3) // original unchanged
}PriorityQueue
type PriorityQueue[A]impl Default for PriorityQueue[K]impl Show for PriorityQueue[A]impl ToJson for PriorityQueue[A]impl Debug for PriorityQueue[A]PriorityQueue::PriorityQueue
#as_free_fn(of, deprecated="Use from_array instead")
#alias(of, deprecated="Use from_array instead")
#as_free_fn(from_array)
#alias(from_array)
fn[A : Compare + Eq] PriorityQueue::PriorityQueue(arr : ArrayView[A]) -> PriorityQueue[A]Creates a new priority queue from an array.
Example
test {
let queue = @priority_queue.PriorityQueue([1, 2, 3, 4, 5])
@test.assert_eq(queue.length(), 5)
}PriorityQueue::clear
Clears the queue.
Example
test {
let queue = @priority_queue.from_array([1, 2, 3, 4])
queue.clear()
@test.assert_eq(queue.length(), 0)
}PriorityQueue::copy
#alias(clone, deprecated="`clone` is deprecated, use `copy` instead")
fn[A] PriorityQueue::copy(self : PriorityQueue[A]) -> PriorityQueue[A]Returns a deep copy of the queue.
Example
test {
let queue = @priority_queue.from_array([1, 2, 3, 4])
let queue2 = queue.copy()
inspect(queue2.length(), content="4")
}PriorityQueue::from_iter
#as_free_fn(from_iterator, deprecated="Use PriorityQueue::from_iter instead.")
#alias(from_iterator, deprecated="`from_iterator` is deprecated, use `from_iter` instead")
#as_free_fn
fn[K : Compare + Eq] PriorityQueue::from_iter(iter : Iter[K]) -> PriorityQueue[K]Creates a priority queue from an iterator of values.
PriorityQueue::is_empty
Checks if the priority queue is empty.
Example
test {
let queue : @priority_queue.PriorityQueue[Int] = PriorityQueue([])
@test.assert_eq(queue.is_empty(), true)
}PriorityQueue::iter
#alias(iterator, deprecated="`iterator` is deprecated, use `iter` instead")
fn[A : Compare + Eq] PriorityQueue::iter(self : PriorityQueue[A]) -> Iter[A]Returns an iterator over elements in descending priority order.
PriorityQueue::length
Returns the number of elements in the queue.
PriorityQueue::new
#as_free_fn(deprecated="Use `PriorityQueue([])` instead")
#deprecated("Use `PriorityQueue([])` instead")
fn[A] PriorityQueue::new() -> PriorityQueue[A]Creates a new empty priority queue.
Deprecated: use PriorityQueue([]) instead.
PriorityQueue::peek
Peeks at the first value in the priority queue, which returns None if the priority queue is empty.
Example
test {
let queue = @priority_queue.from_array([1, 2, 3, 4])
let first = queue.peek() // Some(4)
@test.assert_eq(first, Some(4))
}PriorityQueue::pop
Pops the first value from the priority queue, which returns None if the queue is empty.
Example
test {
let queue = @priority_queue.from_array([1, 2, 3, 4])
let first = queue.pop() // Some(4)
@debug.debug_inspect(first, content="Some(4)")
inspect(queue.length(), content="3")
}PriorityQueue::push
Adds a value to the priority queue.
Example
test {
let queue = @priority_queue.PriorityQueue([])
queue.push(1)
@test.assert_eq(queue.length(), 1)
}PriorityQueue::to_array
Returns an array of all elements in descending priority order.
Install
Installed by default
corestandard library
Apache-2.0
Updated 13 days ago