The d-ary heap « Jim's Random Notes
The answer to the question of the optimal value for d is, as you might expect, “it depends.” The math indicates that a 3-heap should be faster than a 2-heap, a 4-heap about the same speed, and a 5-heap slightly slower. My testing shows that the optimum value is usually three or four, and sometimes a 5-heap outperforms those. I’ve yet to find a case where a 2-heap outperforms a 3-heap. I’m going to ask you to trust me on that until we get the thing built and put it through its paces. Then we can compare the theoretical performance against real-world data.
Java Implementation:
http://en.algoritmy.net/article/41909/D-ary-heap
http://www.sanfoundry.com/java-program-implement-d-ary-heap/
Read full article from The d-ary heap « Jim's Random Notes
In a d-heap, each level you sift down requires d node comparisons.We can’t just increase d and expect better performance. For example, if you were to build a 100-heap (i.e. each node has 100 children), then removing an item from a heap containing 100 items would be like removing from a linear list.
The answer to the question of the optimal value for d is, as you might expect, “it depends.” The math indicates that a 3-heap should be faster than a 2-heap, a 4-heap about the same speed, and a 5-heap slightly slower. My testing shows that the optimum value is usually three or four, and sometimes a 5-heap outperforms those. I’ve yet to find a case where a 2-heap outperforms a 3-heap. I’m going to ask you to trust me on that until we get the thing built and put it through its paces. Then we can compare the theoretical performance against real-world data.
Java Implementation:
http://en.algoritmy.net/article/41909/D-ary-heap
http://www.sanfoundry.com/java-program-implement-d-ary-heap/
Read full article from The d-ary heap « Jim's Random Notes
