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.

Referências

  1. ↑ Gerth Stølting Brodal (1996). Worst-case efficient priority queues. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
  2. ↑ Gerth Stølting Brodal and Chris Okasaki (1996). Optimal purely functional priority queues. J. Functional Programming.
  3. 1 2 3 4 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. [S.l.]: MIT Press and McGraw-Hill
  4. ↑ Fredman, Michael Lawrence; Tarjan, Robert E. «Fibonacci heaps and their uses in improved network optimization algorithms» (PDF). July 1987. Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874
  5. ↑ Brodal, Gerth S. (1996), «Worst-Case Efficient Priority Queues» (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
  6. ↑ Goodrich, Michael T.; Tamassia, Roberto (2004). «7.3.6. Bottom-Up Heap Construction». Data Structures and Algorithms in Java 3rd ed. [S.l.: s.n.] pp. 338–341. ISBN 0-471-46983-1
Ícone de esboço Este artigo sobre estrutura de dados é um esboço. Você pode ajudar a Wikipédia expandindo-o.