12

I'm trying to find more resources regarding Brodal heap. All I found is a haskell implementation of Brodal-Okasaki heap, but I think that they are skew heaps, is this correct? Furthermore, I'm illiterate in Haskell so that does not help much. Does anyone have (or know of) an Brodal queue implementation in pseudocode, C, C++, Python?

Also please correct if my assumptions above are wrong.

Kimvais
  • 391
  • 1
  • 3
  • 11
  • 3
    Are you looking to implement the Brodal queue specifically, or are you looking for an efficient implementation of a priority queue? Brodal mentioned in the conclusion of his paper that they are not practical without some further research in the area. His paper has been quoted extensively, maybe something useful? The CLR Introduction to Algorithms has a section on priority queues, but it references a much earlier work in priority queues. – Jay Elston Oct 10 '11 at 04:33
  • 2
    The original Brodal queue uses destructive assignment, so the Haskell version must have some modifications. – Fred Foo Feb 11 '12 at 12:17

2 Answers2

2

The Haskell implementation is based on the functional Brodal-Okasaki heap and you are right, it is a variation of skew heaps. The paper is written very clearly, so it would be a good resource.

Regarding implementation, there's also an implementation in Scala as part of the scalaz library.

maayank
  • 121
  • 3
1

This is a partial answer since I've not yet figured out how to translate the code into something that's not Haskell. The reason as far as I can tell for them having to use Haskell is that Haskell is lazy. The Brodal-Okasaki heap needs to be implimented in a lazy fashion from the paper. So what you'd need is a way of providing that functionality to another language along with any other requirements (such as purely functional data structures) that the BO Heap might need.