<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
<title></title>
</head>
<body text="#000000" bgcolor="#ffffff">
On 12/20/2010 05:23 PM, Seth Hoenig wrote:
<blockquote
cite="mid:AANLkTinvN3yTyhn4QO4J=fEBhvQ1AN74=Qcc8_OcZ82-@mail.gmail.com"
type="cite"><br>
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt
0.8ex; border-left: 1px solid rgb(204, 204, 204);
padding-left: 1ex;"><font color="#888888">
</font>I think they'd be a good addition to std.container.<br>
</blockquote>
<br>
</div>
Why? What more do you need that std.container.BinaryHeap doesn't
provide?<br>
</blockquote>
An amortised running time of<br>
<br>
O(a + b log(n))<br>
<br>
where a = number of insert + find-min + decrease-key + merge
operations<br>
and b = number of delete and delete-min operations.<br>
<br>
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<br>
<br>
O(m log(n)) algorithm to an O(m + n log(n)) algorithm.<br>
<br>
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. <br>
<br>
Matthias<br>
</body>
</html>