www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - thin heaps

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Just saw this:

http://www.reddit.com/r/programming/comments/eoq15/implementing_shortest_path_in_c_is_much_easier/

in which a reader points to this paper on thin heaps:

http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/thin%20heap.pdf

Does anyone here have experience with thin heaps? I think they'd be a 
good addition to std.container.


Andrei
Dec 20 2010
next sibling parent Seth Hoenig <seth.a.hoenig gmail.com> writes:
--0022150470b72750af0497def929
Content-Type: text/plain; charset=ISO-8859-1

 I think they'd be a good addition to std.container.

Why? What more do you need that std.container.BinaryHeap doesn't provide? --0022150470b72750af0497def929 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"m= argin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); paddin= g-left: 1ex;"><font color=3D"#888888"> </font>I think they&#39;d be a good addition to std.container.<br></blockqu= ote>=A0<br></div>Why? What more do you need that std.container.BinaryHeap d= oesn&#39;t provide?<br> --0022150470b72750af0497def929--
Dec 20 2010
prev sibling next sibling parent Matthias Walter <xammy xammy.homelinux.net> writes:
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit

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?

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
Dec 20 2010
prev sibling next sibling parent Matthias Walter <xammy xammy.homelinux.net> writes:
On 12/20/2010 05:01 PM, Andrei Alexandrescu wrote:
 Just saw this:

 http://www.reddit.com/r/programming/comments/eoq15/implementing_shortest_path_in_c_is_much_easier/


 in which a reader points to this paper on thin heaps:

 http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/thin%20heap.pdf


 Does anyone here have experience with thin heaps? I think they'd be a
 good addition to std.container.

priority queue. In fact I thought about implementing Fibonacci Heaps with the same interface for D. I worked on a C++ implementation a while ago, so maybe I should give the Thin Heaps a try? Matthias
Dec 20 2010
prev sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 20/12/10 10:01 PM, Andrei Alexandrescu wrote:
 Just saw this:

 http://www.reddit.com/r/programming/comments/eoq15/implementing_shortest_path_in_c_is_much_easier/


 in which a reader points to this paper on thin heaps:

 http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/thin%20heap.pdf


 Does anyone here have experience with thin heaps? I think they'd be a
 good addition to std.container.


 Andrei

I don't know what the constants are, but Soft Heaps apparently have constant time for all operations: http://en.wikipedia.org/wiki/Soft_heap
Dec 21 2010