Skip to content

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 ​

SyntaxDescription
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 ​

MethodSignatureReturnsDescription
push(T) => voidvoidInsert 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() => usizeusizeNumber of elements
isEmpty() => booleanbooleanWhether the heap has no elements
clear() => voidvoidRemove all elements

The native handle is released automatically when the binding goes out of scope.

Complexity ​

OperationTime Complexity
pushAmortized O(1), worst-case O(log n)
popO(log n)
peekO(log n)
lenO(1)
isEmptyO(1)
clearO(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 ​

tyrus
import { BinomialHeap } from "tyrus:algorithm";

const bh = BinomialHeap<i32>();

push ​

tyrus
const bh = BinomialHeap<i32>();

bh.push(10);
bh.push(3);
bh.push(7);

print(bh.len());  // 3

pop ​

tyrus
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);  // -1

peek ​

tyrus
const bh = BinomialHeap<i32>();

bh.push(10);
bh.push(3);

const top: i32? = bh.peek();
if (top) {
    print(top);  // 10
}

len ​

tyrus
const bh = BinomialHeap<i32>();

print(bh.len());  // 0

bh.push(5);
bh.push(1);

print(bh.len());  // 2

isEmpty ​

tyrus
const bh = BinomialHeap<i32>();

print(bh.isEmpty());  // true

bh.push(1);

print(bh.isEmpty());  // false

clear ​

tyrus
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