Heap (std)
std/heap is written in Agentica: import Heap from "std/heap".
A heap is an immutable Heap.Heap[T] value that holds values of any type. You give the order to new as a function before: it is true when its first value comes out before its second, so a < b gives the smallest first and a > b the largest first. Give a strict order (< or >, not <=); the heap still works with a non-strict one, but values that tie come out in no set order either way. Every function gives a new heap; assign it to keep it, or continue with Popped.remaining. pop and peek on an empty heap return an error Result of kind heap.empty.
push and pop take O(log n) steps; peek, size and empty? take O(1).
Heap.new and Heap.from #
Heap.new(before: Fn[T, T, Bool]) -> Heap.Heap[T]
Heap.from(values: List[T], before: Fn[T, T, Bool]) -> Heap.Heap[T]new gives an empty heap; from pushes every value of a list.
import Heap from "std/heap"
def main() -> Void
empty = Heap.new do |a: Int, b: Int| a < b end
puts(Heap.size(empty))
largest = Heap.from(["fig", "pear", "apple"]) do |a: String, b: String| a.compare(b) > 0 end
puts(Heap.peek(largest))
end0
ok("pear")Heap.push #
Heap.push(heap: Heap.Heap[T], value: T) -> Heap.Heap[T]Adds a value.
import Heap from "std/heap"
def main() -> Void
h = Heap.new do |a: Int, b: Int| a < b end
h = Heap.push(h, 3)
h = Heap.push(h, 1)
puts(Heap.peek(h))
endok(1)Heap.pop #
Heap.pop(heap: Heap.Heap[T]) -> Result[Heap.Popped[T]]Takes the first value. It gives a Popped with value and the remaining heap, or an error when the heap is empty.
import Heap from "std/heap"
struct Job
name: String
priority: Int
end
def main() -> Void
jobs = [Job(name: "mail", priority: 2), Job(name: "backup", priority: 9), Job(name: "log", priority: 5)]
h = Heap.from(jobs) do |a: Job, b: Job| a.priority > b.priority end
popped = Heap.pop(h).unwrap!
puts(popped.value.name)
puts(Heap.size(popped.remaining))
endbackup
2Heap.peek #
Heap.peek(heap: Heap.Heap[T]) -> Result[T]Reads the first value without removing it.
import Heap from "std/heap"
def main() -> Void
h = Heap.new do |a: Int, b: Int| a < b end
puts(Heap.peek(h).ok?)
puts(Heap.peek(Heap.push(h, 7)))
endfalse
ok(7)Heap.size and Heap.empty? #
Heap.size(heap: Heap.Heap[T]) -> Int
Heap.empty?(heap: Heap.Heap[T]) -> Boolimport Heap from "std/heap"
def main() -> Void
h = Heap.new do |a: Int, b: Int| a < b end
puts(Heap.empty?(h))
h = Heap.push(h, 4)
puts(Heap.empty?(h))
puts(Heap.size(h))
endtrue
false
1Heap.to_a #
Heap.to_a(heap: Heap.Heap[T]) -> List[T]Gives every value in the order pop takes them, in O(n log n).
import Heap from "std/heap"
def main() -> Void
h = Heap.from([5, 1, 4, 2]) do |a: Int, b: Int| a < b end
puts(Heap.to_a(h))
end[1, 2, 4, 5]