Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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 4:33
The original Brodal queue uses destructive assignment, so the Haskell version must have some modifications. – Fred Foo Feb 11 '12 at 12:17

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.

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.