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
Predefinição:Heap complexidade
Predefinição:Esboço-estrutura de dados Predefinição:Estrutura de dados Predefinição:Árvores (estrutura de dados)
- ↑ 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.