Re: [boost] status of fibonnaci_heap and mutable_queue

From: David Abrahams (dave_at_[hidden])
Date: 2006-04-13 12:16:00

Douglas Gregor <doug.gregor_at_[hidden]> writes:

> On Apr 12, 2006, at 5:10 PM, David Abrahams wrote:
>
>> Douglas Gregor <doug.gregor_at_[hidden]> writes:
>>
>>> This would change the complexity of Dijkstra's algorithm from O(|V|
>>> lg |V|) to O(|V| lg |E|), where |V| is the number of vertices in the
>>> graph and |E| is the number of edges in the graph.
>>
>> Hmm, did you see:
>> http://lists.boost.org/Archives/boost/2002/01/23970.php
>> and the foregoing thread?
>
> I've read it now. So I'll be more careful with the complexity measures:
>
> With a relaxed heap it's O(|V| lg |V| + |E|)
> With a binary heap it's O((|V| + |E|) lg |V|)
>
> If you insert instead of updating, that, lg |V| becomes a lg |E|.
>
> The relaxed heap is admittedly complicated. 

More importantly to me, it makes usage requirements much more
complicated in some cases.

> We have some performance test's we've run, and it's a toss-up. On
> some graphs, the binary heap does slightly better; on others, the
> relaxed heap does slightly better.

Well, that's great to know.

So, I'll ask my original question again: given that it's a toss-up,
and it is often inconvenient for users, does it make sense to require
a relaxed heap?

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com