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.[1]
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.[2]
Resumo dos tempos de execução[editar | editar código-fonte]
Nas seguintes complexidades de tempo[3] 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[3] | Binomial[3] | Fibonacci[3][4] | Brodal[5][a] |
|---|---|---|---|---|
| encontrar-min | Θ(1) | Θ(log n) | Θ(1) | Θ(1) |
| remover-min | Θ(log n) | Θ(log n) | O(log n)[b] | O(log n) |
| inserção | O(log n) | Θ(1)[b] | Θ(1) | Θ(1) |
| diminuir-chave | Θ(log n) | Θ(log n) | Θ(1)[b] | Θ(1) |
| merge | Θ(n) | O(log n)[c] | Θ(1) | Θ(1) |
Referências
- ↑ Gerth Stølting Brodal (1996). Worst-case efficient priority queues. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
- ↑ Gerth Stølting Brodal and Chris Okasaki (1996). Optimal purely functional priority queues. J. Functional Programming.
- ↑ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. [S.l.]: MIT Press and McGraw-Hill
- ↑ 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
- ↑ Brodal, Gerth S. (1996), «Worst-Case Efficient Priority Queues» (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
- ↑ 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
