Skip to content

BinomialHeap ​

BinomialHeap<T> implementa una cola de prioridad max-heap como un bosque de árboles binomiales implementado por el runtime nativo. A diferencia de un binary heap, que mantiene un único array contiguo, el binomial heap guarda sus elementos en una colección de árboles binomiales cuyos tamaños son los dígitos binarios del recuento de elementos, por lo que fusionar dos colas cuesta O(log n) en lugar de reconstruir toda la estructura.

Construcción ​

SintaxisDescripción
BinomialHeap<T>()Crea una nueva cola vacía

El parámetro de tipo T determina el tipo del elemento. T debe ser un tipo numérico ordenable (i8–i128, u8–u128, f32, f64 o f128).

Métodos ​

MétodoFirmaDevuelveDescripción
push(T) => voidvoidInserta un elemento
pop() => T?T?Elimina y devuelve el elemento más grande, o vacío si está vacía
peek() => T?T?Devuelve el elemento más grande sin eliminarlo, o vacío si está vacía
len() => usizeusizeNúmero de elementos
isEmpty() => booleanbooleanSi la cola no tiene elementos
clear() => voidvoidElimina todos los elementos

El handle nativo se libera automáticamente cuando la variable sale del ámbito.

Complejidad ​

OperaciónComplejidad Temporal
pushAmortizado O(1), peor caso O(log n)
popO(log n)
peekO(log n)
lenO(1)
isEmptyO(1)
clearO(n)

peek() recorre la lista de raíces, por lo que cuesta O(log n) en lugar del O(1) de un binary heap. push cuesta O(1) amortizado porque la mayoría de las inserciones solo añaden un árbol nuevo a la lista de raíces; un pop que lo elimina reconstruye la cola en O(log n).

Ejemplos ​

Construcción ​

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