[Lemon-user] Fibonnaci Heap

[Kovács Péter]

Dear Peter,

> Dear LEMON Users,
> from what I read, Fibonacci Heaps are faster than Binary Heaps.

Theoretically, Fibonacci heaps are faster, but in practice, they are 
usually slower than the standard binary heaps. Actually, it depends on 
the use case, which heap implementation is the most efficient.

> The latter ones work well in LEMON. The first I just can get to work.
> There is always a EXC_BAD_ACCESS.

Isn't it caused by pushing the same arc (with id 0) twice to the heap?

> Why is this happening?
> Is it really worth to use FibHeaps? I have to push many arc into the heap.
>
> Thank you very much!

As I wrote above, it depends on your use case. You may either perform 
some benchmarks or simply use binary heaps (they are rather efficient is 
most cases).

Some benchmark results of LEMON's heap implementations applied in 
Dijkstra's algorithm can be found here:
https://lemon.cs.elte.hu/trac/lemon/attachment/ticket/313/heap_benchmark_results.txt

Best regards,
Peter


>
> int main(){
> FullGraph                   f(1000);
> FullGraph::ArcMap< int >    cost( f );
> FullGraph::ArcMap< int >    fibHeapMap( f );
> FibHeap< int, FullGraph::ArcMap<int> >    myFibHeap( fibHeapMap );
>
>
> for (FullGraph::ArcIt a( f ); a!=INVALID; ++a) {
>          cost[a] = rnd.integer( 100 );
>      }
>
>
> // --- first
>      myFibHeap.push( f.arcFromId( 0 ), 3 );
>
>
> // --- second
> for (FullGraph::ArcIt a( f ); a!=INVALID; ++a){
>          myFibHeap.push( a, cost[ a ]);
>      }
>    }
>
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>