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

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][lower-alpha 1]
encontrar-min Θ(1) Θ(log n) Θ(1) Θ(1)
remover-min Θ(log n) Θ(log n) O(log n)[lower-alpha 2] O(log n)
inserção O(log n) Θ(1)[lower-alpha 2] Θ(1) Θ(1)
diminuir-chave Θ(log n) Θ(log n) Θ(1)[lower-alpha 2] Θ(1)
merge Θ(n) O(log n)[lower-alpha 3] Θ(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).[6]
  2. 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. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.