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
| Sintaxe | Descriçã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étodo | Assinatura | Retorna | Descrição |
|---|---|---|---|
push | (T) => void | void | Insere 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 | () => usize | usize | Número de elementos |
isEmpty | () => boolean | boolean | Se a fila não tem elementos |
clear | () => void | void | Remove todos os elementos |
O handle nativo é liberado automaticamente quando a variável sai de escopo.
Complexidade
| Operação | Complexidade Temporal |
|---|---|
push | Amortizado O(1), pior caso O(log n) |
pop | O(log n) |
peek | O(log n) |
len | O(1) |
isEmpty | O(1) |
clear | O(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
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