thin heaps

[Matthias Walter]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20101220/4c82f6d7/attachment.html>