Fila Brodal

Em ciência da computação, a fila Brodal é uma heap/fila de prioridade com nível muito baixo no seu pior caso de tempo de complexidade: sendo  para a inserção, encontrar-mínimo, fundir (merge de duas filas) e diminuir-chave, e para remover-mínimo e remoções gerais. Eles são a primeira variante de uma heap a atingir estes limites, sem recorrer a amortização dos custos operacionais. Filas Brodal são nomeados após serem inventadas por Gerth Stølting Brodal.

Apesar de ter o melhores tempos assintóticos que outras filas de prioridade, elas são, nas palavras do próprio Brodal, "muito complicadas" e "não aplicáveis na prática." Brodal e Okasaki descreverem uma versão persistente (puramente funcional) de filas Brodal.

Resumo dos tempos de execução

Nas seguintes complexidades de tempo O(f) é um limite assintótico superior e Θ(f) é um limite assintótico estreito (ver Notação Big O). Os nomes das funções assumem que é um min-heap.

Operação Binária Binomial Fibonacci Brodal
encontrar-min Θ(1) Θ(log n) Θ(1) Θ(1)
remover-min Θ(log n) Θ(log n) O(log n) O(log n)
inserção O(log n) Θ(1) Θ(1) Θ(1)
diminuir-chave Θ(log n) Θ(log n) Θ(1) Θ(1)
merge Θ(n) O(log n) Θ(1) Θ(1)
  1. ↑ Brodal e Okasaki descrevem mais tarde uma variante persistente com os mesmos limites, exceto para o diminuir-chave, que não é suportado. Heaps com n elementos podem ser construídas de baixo-para-cima em O(n).
  2. 1 2 3 Tempo amortizado.
  3. ↑ n é o tamanho do maior heap.