Skip to content

BinomialHeap ​

BinomialHeap<T> implementa uma fila de prioridade max-heap como uma floresta de árvores binomiais implementada pelo runtime nativo. Diferente de um binary heap, que mantém um único array contíguo, o binomial heap guarda seus elementos numa coleção de árvores binomiais cujos tamanhos são os dígitos binários da contagem de elementos, então unir duas filas custa O(log n) em vez de reconstruir a estrutura inteira.

Construção ​

SintaxeDescrição
BinomialHeap<T>()Cria uma nova fila vazia

O parâmetro de tipo T determina o tipo do elemento. T deve ser um tipo numérico ordenável (i8–i128, u8–u128, f32, f64 ou f128).

Métodos ​

MétodoAssinaturaRetornaDescrição
push(T) => voidvoidInsere um elemento
pop() => T?T?Remove e retorna o maior elemento, ou vazio se vazio
peek() => T?T?Retorna o maior elemento sem removê-lo, ou vazio se vazio
len() => usizeusizeNúmero de elementos
isEmpty() => booleanbooleanSe a fila não tem elementos
clear() => voidvoidRemove todos os elementos

O handle nativo é liberado automaticamente quando a variável sai de escopo.

Complexidade ​

OperaçãoComplexidade Temporal
pushAmortizado O(1), pior caso O(log n)
popO(log n)
peekO(log n)
lenO(1)
isEmptyO(1)
clearO(n)

peek() percorre a lista de raízes, então custa O(log n) em vez do O(1) de um binary heap. push custa O(1) amortizado porque a maioria das inserções apenas anexa uma nova árvore à lista de raízes; um pop que a remove reconstrói a fila em O(log n).

Exemplos ​

Construção ​

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