On 12/20/2010 05:23 PM, Seth Hoenig wrote: > > I think they'd be a good addition to std.container. > > > Why? What more do you need that std.container.BinaryHeap doesn't provide? An amortised running time of
O(a + b log(n)) where a = number of insert + find-min + decrease-key + merge operations and b = number of delete and delete-min operations. Binomial heaps need log(n) time also for insert and decrease-key. In fact, graph-algorithms (like Dijkstra's shortest path) do lots of decrease-key operations (for every edge), which improves the O(m log(n)) algorithm to an O(m + n log(n)) algorithm. Of course this is asymptotic behavior (it even needs to be amortised, so only inserting and decreasing keys produces more than linear effort), so you need some medium-sized graphs for this to have an effect for Fibonacci heaps. These tiny-heaps seem to have less overhead than FibHeaps (which needs 3 pointers, a bool and the key itself per item), which might be better for practical implementation. Matthias
