Pseudocódigo para fila Brodal

12

Estou tentando encontrar mais recursos sobre a pilha Brodal . Tudo o que descobri foi uma implementação haskell do heap de Brodal-Okasaki , mas acho que eles são heap de inclinação , isso está correto? Além disso, sou analfabeta em Haskell, de modo que não ajuda muito. Alguém tem (ou conhece) uma implementação de fila Brodal em pseudocódigo, C, C ++, Python?

Também corrija se minhas suposições acima estão erradas.

research data-structures Kimvais
fonte
3
Você está procurando implementar a fila Brodal especificamente ou está procurando uma implementação eficiente de uma fila prioritária? Brodal mencionou na conclusão de seu artigo que eles não são práticos sem mais pesquisas na área. Seu artigo foi citado extensivamente, talvez algo útil? A Introdução aos algoritmos do CLR possui uma seção sobre filas prioritárias, mas faz referência a um trabalho muito anterior nas filas prioritárias.
Jay Elston
2
A fila Brodal original usa atribuição destrutiva, portanto a versão Haskell deve ter algumas modificações.
Fred Foo

Respostas:

2

A implementação do Haskell é baseada no heap funcional Brodal-Okasaki e você está certo, é uma variação de heap de inclinação. O artigo foi escrito com muita clareza, por isso seria um bom recurso.

Em relação à implementação, também há uma implementação no Scala como parte da biblioteca scalaz.

maayank
fonte
1

Esta é uma resposta parcial, pois ainda não descobri como traduzir o código em algo que não é Haskell. A razão, pelo que sei, para eles terem que usar Haskell é que Haskell é preguiçoso. A pilha de Brodal-Okasaki precisa ser implementada de maneira preguiçosa a partir do jornal. Portanto, o que você precisa é uma maneira de fornecer essa funcionalidade para outro idioma, juntamente com outros requisitos (como estruturas de dados puramente funcionais) que o BO Heap possa precisar.

Engenheiro Mundial
fonte