binary heap vs binomial heap vs fibonacci heap, regarding performance for a priority queue
https://stackoverflow.com/questions/8353038
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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!
Solution
You might find the third article in http://themonadreader.files.wordpress.com/2010/05/issue16.pdf relevant.
OTHER TIPS
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.
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:
Binomial Heap:
Fibonacci Heap:
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.
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.
