Fila Brodal
De Wikipedia, a enciclopédia encyclopedia
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]