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!

Throoze
  • 3,988
  • 8
  • 45
  • 67
  • 1
    Eh, if this is the first time you're implementing a heap, just write a version using a binary heap first. Just make it abstract enough so that you can replace it with something else if you *really* have to. Binomial and Fibonacci heaps are much more complicated than binary ones, and are probably not worth struggling with (unless you just want to learn about them, of course). – Tikhon Jelvis Dec 02 '11 at 10:03
  • I like Leonardo heaps most. They appear in Dijkstras Smoothsort. – fuz Dec 02 '11 at 16:57
  • 1
    Implement them all and benchmark them with your application. – augustss Dec 02 '11 at 19:10
  • @TikhonJelvis: well, I would like to learn about all of them. I posed this question because I need to choose one for this project (it's for college), but I would like to know which one is the best, and implementation tricks. For this project, I'm asked to have at most O(log n) time in insertion and extractMin operations. I'm know both binomial and fibonacci provide this time, but I would like to know how to choose. I don't know if binary is faster or slower than that, but well, that's my question! which one I choose? and why? thanks! – Throoze Dec 02 '11 at 23:50
  • 1
    Check out [this](http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants) article. It lists the different times. You'll find a binary heap also satisfies your constraints. Since the binary heap is much simpler and more elegant, I would suggest using it even though the others may have better performance. – Tikhon Jelvis Dec 03 '11 at 00:02
  • Definitely go with the simpler one first. In software engineering its always the rule to assume that the simpler solution will be good enough, and then optimise it after you have the measurements. Trying to guess without evidence will simply cause you to waste effort. – Paul Johnson Dec 03 '11 at 11:57
  • 2
    Might want to see [what-is-the-difference-between-binary-heaps-and-binomial-heaps?](http://stackoverflow.com/questions/6215485), [when-to-use-binomial-heap?](http://stackoverflow.com/questions/20096084), [what-is-the-intuition-behind-the-fibonacci-heap-data-structure](http://stackoverflow.com/questions/19508526), [real-world-applications-of-binary-heaps-and-fibonacci-heaps](http://stackoverflow.com/questions/3767863), [efficient-heaps-in-purely-functional-languages](http://stackoverflow.com/questions/932721) – nawfal Jun 15 '14 at 08:55
  • possible duplicate of [Efficient heaps in purely functional languages](http://stackoverflow.com/questions/932721/efficient-heaps-in-purely-functional-languages) – Ciro Santilli OurBigBook.com Jun 20 '15 at 06:30

4 Answers4

4

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

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • On the third article, on page 45, when they define the `data Succ rk a = BinomTree rk a ? rk a`, there's a funny symbol, like a laid triangle, before the second rk a (instead of the '?' symbol I wrote)... I'm not very used to haskell syntax, could you please explain me what does that symbol mean?? thanks! – Throoze Dec 04 '11 at 05:22
  • 1
    @Throoze: The weird triangle is merely an infix data constructor for the type `Succ`. You can read that line as: `data Succ rk a = Succ (BinomTree rk a) (rk a)` – opqdonut Dec 04 '11 at 15:42
  • 1
    It's just a symbol to make the paper more readable. When writing the actual program, I typically write the infix constructor ":<:" opqdonut's explanation works, too. – Louis Wasserman Dec 05 '11 at 06:10
  • 1
    (Also, full disclosure: I am the author of that article.) – Louis Wasserman Dec 05 '11 at 06:11
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

Community
  • 1
  • 1
opqdonut
  • 5,119
  • 22
  • 25
1

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.

Larry LIU Xinyu
  • 2,003
  • 1
  • 13
  • 10
1

They have different time complexity on different operations on Priority Queue. Here is a visual table for you

╔══════════════╦═══════════════════════╦════════════════════════╦══════════════════════════════╗
║  Operation   ║       Binary          ║      Binomial          ║       Fibonacci              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║   insert     ║      O(logN)          ║      O(logN)           ║         O(1)                 ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║  find Min    ║       O(1)            ║      O(logN)           ║         O(1)                 ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║   Revmove    ║       O(logN)         ║      O(logN)           ║        O(logN)               ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║ Decrease Key ║       O(logN)         ║      O(logN)           ║        O(1)                  ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║                       ║                        ║                              ║
║    Union     ║         O(N)          ║      O(logN)           ║        O(1)                  ║
║              ║                       ║                        ║                              ║
╠══════════════╬═══════════════════════╬════════════════════════╬══════════════════════════════╣
║              ║ ■ Min element is root ║order k binomial tree Bk║ ■ Set of heap-ordered trees. ║
║              ║ ■ Heap height = logN  ║ ■ Number of nodes = 2k.║ ■ Maintain pointer to min.   ║
║              ║                       ║ ■ Height = k.          ║   (keeps find min/max O(1))  ║                        
║              ║                       ║ ■ Degree of root = k.  ║ ■ Set of marked nodes.       ║
║  Useful      ║                       ║ ■ Deleting root yields ║   (keep the heaps flat)      ║
║  Properties  ║                       ║   binomial trees       ║                              ║
║              ║                       ║   Bk-1, … , B0.        ║                              ║
║              ║                       ║   (see graph below)    ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║
║              ║                       ║                        ║                              ║             
╚══════════════╩═══════════════════════╩════════════════════════╩══════════════════════════════╝

I got this image from the Princeton lecture slides

Binary Heap: enter image description here

Binomial Heap:

k bonomial trees

Fibonacci Heap:

enter image description here

Note: Binomial and Fibonacci Heap looks familiar but they are subtly different:

  • Binomial heap: eagerly consolidate trees after each insert.
  • Fibonacci heap: lazily defer consolidation until next delete-min.
OLIVER.KOO
  • 5,654
  • 3
  • 30
  • 62