geeksforgeeks - binary heap vs binomial heap vs fibonacci heap, regarding performance for a priority queue
fibonacci heap geeksforgeeks (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 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.
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...
Some reference to functional Binomial heap, Fibonacci Heap and Pairing heap: https://github.com/downloads/liuxinyu95/AlgoXY/kheap-en.pdf
If the performance is really the issue, I suggest using pairing heap. The only risk is that it's performance is still a conjecture till now. But experiments show that the performance is quite good.
You might find the third article in http://themonadreader.files.wordpress.com/2010/05/issue16.pdf relevant.