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
| Sintaxis | Descripció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étodo | Firma | Devuelve | Descripción |
|---|---|---|---|
push | (T) => void | void | Inserta 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 | () => usize | usize | Número de elementos |
isEmpty | () => boolean | boolean | Si la cola no tiene elementos |
clear | () => void | void | Elimina todos los elementos |
El handle nativo se libera automáticamente cuando la variable sale del ámbito.
Complejidad
| Operación | Complejidad Temporal |
|---|---|
push | Amortizado O(1), peor caso O(log n) |
pop | O(log n) |
peek | O(log n) |
len | O(1) |
isEmpty | O(1) |
clear | O(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
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