• Andrei Alexandrescu (7/7) Dec 20 2010 Just saw this:
• Seth Hoenig (1/2) Dec 20 2010 Why? What more do you need that std.container.BinaryHeap doesn't provide...
• Matthias Walter (16/19) Dec 20 2010 An amortised running time of
• Matthias Walter (6/12) Dec 20 2010 You might have realized my recent interest in std.container.BinHeap as a
• Peter Alexander (3/10) Dec 21 2010 I don't know what the constants are, but Soft Heaps apparently have

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

Seth Hoenig <seth.a.hoenig gmail.com> writes:

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

Why? What more do you need that std.container.BinaryHeap doesn't provide?

Matthias Walter <xammy xammy.homelinux.net> writes:

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

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.

You might have realized my recent interest in std.container.BinHeap as a
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

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