Alex Rivera | Logout

binary heap vs binomial heap vs fibonacci heap, regarding performance for a priority queue

Asked 2011-12-02T07:28:10.660
12

Could someone please explain me how should I decide whether to use one or another heap implementation, among the ones mentioned in the title?

I would like an answer to guide me on choosing the implementation regarding the performance of the structure, according to the problem. Right now, I'm doing a priority queue, but I would like to know not only the most appropriate implementation for this case, but the basics that allow me to choose an implementation in any other situation...

Other thing to consider is that I'm using haskell this time, so, if you know of any trick or something that would improve the implementation with this language, please let me know! but as before, comments about using other languages are welcome too!

Thanks! and sorry if the question is too basic, but i'm not familiar with heaps at all. This is the first time i'm facing the task of implementing one...

thanks again!

performance haskell fibonacci binary-heap binomial-heap
Edit
Report

2 Answers

4

You might find the third article in http://themonadreader.files.wordpress.com/2010/05/issue16.pdf relevant.

answered 2011-12-03T21:48:19.893
3

First of all, you won't be implementing a standard heap in Haskell. You'll instead be implementing a persistent and functional heap. Sometimes the functional versions of classical data structures are as performant as the original (e.g. simple binary trees) but sometimes not (e.g. simple queues). In the latter case you will need a specialized functional data structure.

If you are not familiar with functional data structures, I suggest starting with Okasaki's great book or thesis (chapters of interest: at least 6.2.2, 7.2.2).

If all of that went over your head, I suggest starting with implementing a simple linked binary heap. (Making an efficient array-based binary heap in Haskell is a bit tedious.) Once that is done, you could try your hand at implementing a binomial heap by using Okasaki's pseudo code or even starting from scratch.

PS. This cstheory.se answer is great

answered 2011-12-04T15:38:26.697

Your Answer