BinomialHeap
BinomialHeap<T> implements a max-heap priority queue as a forest of binomial trees implemented in the native runtime. Unlike a binary heap, which keeps a single contiguous array, the binomial heap stores its elements in a collection of binomial trees whose sizes are the binary digits of the element count, so merging two heaps costs O(log n) instead of rebuilding the whole structure.
Construction
| Syntax | Description |
|---|---|
BinomialHeap<T>() | Create a new empty heap |
The type parameter T determines the element type. T must be an ordered numeric type (i8–i128, u8–u128, f32, f64, or f128).
Methods
| Method | Signature | Returns | Description |
|---|---|---|---|
push | (T) => void | void | Insert an element |
pop | () => T? | T? | Remove and return the largest element, or empty if empty |
peek | () => T? | T? | Return the largest element without removing it, or empty if empty |
len | () => usize | usize | Number of elements |
isEmpty | () => boolean | boolean | Whether the heap has no elements |
clear | () => void | void | Remove all elements |
The native handle is released automatically when the binding goes out of scope.
Complexity
| Operation | Time Complexity |
|---|---|
push | Amortized O(1), worst-case O(log n) |
pop | O(log n) |
peek | O(log n) |
len | O(1) |
isEmpty | O(1) |
clear | O(n) |
peek() walks the root list, so it is O(log n) rather than the O(1) of a binary heap. push takes amortized O(1) because most inserts only append a new tree to the root list; a pop that removes it rebuilds the heap in O(log n).
Examples
Construction
import { BinomialHeap } from "tyrus:algorithm";
const bh = BinomialHeap<i32>();push
const bh = BinomialHeap<i32>();
bh.push(10);
bh.push(3);
bh.push(7);
print(bh.len()); // 3pop
const bh = BinomialHeap<i32>();
bh.push(10);
bh.push(3);
bh.push(7);
const p1: i32? = bh.pop();
if (p1) {
print(p1); // 10
}
const p2: i32? = bh.pop();
if (p2) {
print(p2); // 7
}
const p3: i32? = bh.pop();
if (p3) {
print(p3); // 3
}
const p4: i32? = bh.pop();
print(p4 ?? -1); // -1peek
const bh = BinomialHeap<i32>();
bh.push(10);
bh.push(3);
const top: i32? = bh.peek();
if (top) {
print(top); // 10
}len
const bh = BinomialHeap<i32>();
print(bh.len()); // 0
bh.push(5);
bh.push(1);
print(bh.len()); // 2isEmpty
const bh = BinomialHeap<i32>();
print(bh.isEmpty()); // true
bh.push(1);
print(bh.isEmpty()); // falseclear
const bh = BinomialHeap<i32>();
bh.push(10);
bh.push(3);
bh.push(7);
print(bh.len()); // 3
bh.clear();
print(bh.isEmpty()); // true
print(bh.len()); // 0