## digitalmars.D - thin heaps

• 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:

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

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
```
Dec 20 2010
Peter Alexander <peter.alexander.au gmail.com> writes:
```On 20/12/10 10:01 PM, Andrei Alexandrescu wrote:
Just saw this:

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