Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
2  
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
1  
The original Brodal queue uses destructive assignment, so the Haskell version must have some modifications. –  larsmans Feb 11 '12 at 12:17
add comment

2 Answers

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
add comment

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
add comment

Your Answer

 
discard

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.